当前位置:   article > 正文

一些图论算法_求图的最大环

求图的最大环

1、有向图/无向图最小环/最大环:

   此问题多次考,屡T不爽

    (1)遍历找环

           :不要看到dfs就觉得不好,其实变少的时候dfs比其他找环方式要好得多、、、、;


//无边权://

/*

void 找(int 当前点,int 层数)

   当前点=找过;
for(i=1;i<=后面点数;i++)
{
if(后面点[i]==找过)
{
最小环数/最大环数=   min/max   ( 最小环数/最大环数 ,层数[当前点]-层数[i]) ;
}
else
{
找(i,层数+1); 
}
}
  当前点=没找过; 
}

*/

//有边权://

/*

void 找(int 当前点,int 边权前缀和)
{  
   当前点=找过;  
for(i=1;i<=后面点数;i++)
{
if(后面点[i]==找过)
{
最小环数/最大环数 =  min/max   (  最小环数/最大环数  ,边权前缀和+边权[当前点][i]);
}
else
{
找(i,边权前缀和+边权[当前点][i]); 
}
}
  当前点=没找过; 
}

*/



(2)floyd(适用于边多)

/*

for(k=1;k<=n;k++)
        {
        for(i=1;i<k;i++)
            for(j=1;j<k;j++)
            {
            最小环/最大环=min/max(直达路值[i][k]+直达路值[k][j]+能到达路值[i][j])
    }
        for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
        {
        能到达路值[i][j]=min/max(能到达路值[i][k]+能到达路值[k][j],能到达路值[i][j]);
}
}

*/

2、最短路 

 (1)首推SPFA(因为快)

/*    

队列[1]=起点;
while(队列不空)
{
st=队列尾;
头指针前走;  
st=无访问;
for(i=1;i<=st后的点数;i++)
{
   if(f[st后的点[i]]>f[st]+边权[st][st后的点[i]])
{
f[st后的点[i]]=f[st]+边权[st][st后的点[i]]; 
if(st后的点[i]==无访问)
              {
      st后的点[i]=访问;
      队列加入  st后的点[i];
  }
}
}
}

*/


3、最小生成树

 推荐kruskal算法;

4、最大生成树

  kruskal降序排序即可


5、拓扑排序:

    while(栈不为空)
{
st=栈顶元素;
栈指针+1;
for(i=1;i<=后面点的个数;i++)
{
入度[st][i]--;
if(入度[st][i]==0)
{
栈中加入 st后第i个元素

}


另外,记搜可以解决拓扑排序,而且时间极快(小心栈!);


6、最大流:

1最简EK


邻接表读边;

答案=0;


从起点BFS,找到终点或没有元素时停止;

while

{

找边权最小值,反向建/更新,正向边减;

答案+=最小值;

}


输出答案;;;


7、线段树:


1、建求和树:

void 建树(树编号,数组起点,数组终点)

{

树【树编号】.左=数组起点;

树【树编号】.右=数组终点;

if(起点==终点)树【树编号】.和=数组【数组起点(数组终点)】;

else

{

    建树(树编号*2+1,数组起点,(数组起点+数组终点)/2);

    建树(树编号*2+2,(数组起点+数组终点)/2+1,数组终点);

树【树编号】.和=树【树编号*2+2】.和+树【树编号*2+2】.和 ;

}

}


2、查树:

int  查树(树编号,左,右)

{

中=(树【树编号】.左+树【树编号】.右)/2;

if(左==树【树编号】.左&&右==树【树编号】.右)return 树【树编号】.和;

if(左>中)return 查树(树编号*2+2,左,右);

if(右>=中)return 查树(树编号*2+1,左,右);

return 查树(树编号*2+1,左,中)+查树(树编号*2+2,中+1,右);

}


3、求和数上加减乘除;;;

注意:方法我感觉有一些慢+低效,但好像是正解、、、

自然是先建树,然后更新到每一步操作的区间,再打上标记、、、、、

很好懂的方法,但总感觉更新树太慢、、、、




8、树链剖分:


//两边dfs:

第一遍目的:找重边,找每个点下面点数,找深度;;

第二遍目的:找dfs序,重边的“根”;;


邻接表存储(顺便求出每个点父亲)



第一遍dfs:找重边

void 找重边(int 结点,int当前深度)

{

深度【结点】=当前深度;

int  下面点数最大  的孩子  的点数=0;int  下面点数最大  的  边  =0;

  循环下面孩子

{

   找重边(边的终点,当前深度+1);

   if(最大孩子的数<边的终点的数)

{

   最大孩子的数=边的终点的数;

  最大孩子的 边=边;

}

}

if(最大孩子的边!=0)

{

  重边【结点】=最大孩子的边;

}

}



第二遍dfs:求链

void  求链(int 点,int 根)

{

总数++;

dfs序【总数】=点;

根【点】=根;

if(!重边【点】){    求链(重边【点】的终点,根)}

循环下面孩子

{

if(边不是重边)求链(边的终点,边的终点);

}

}



9、RMQ

思路简洁,代码也好写:

就是记录在  第i个数  到  第i个数后2的几次方  的最值;

查找时   答案=max(第i个数   到 log2(终点-起点), 第 终点-log2(终点-起点)到  log2(终点-起点));



读入f【i】【0】;

for(j=1;j<=20;j++)

{

  for(i=1;i+(1<<j)-1<=n;i++)

{

最大值【i】【j】=max(f【i】【j-1】,f【i+1<<j-1)】【j-1】)

}

}

读入 起点  终点;

对数=log终点-起点/log 2;

输出   max(f【起点】【对数】,f【终点-(1<<对数)+1】【对数】);


10、splay

一只巨大的结构

#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <iostream>
using namespace std;
const int INF = 1e9;
const int MAX_Q = 1e5 + 10;
struct splay_node 
{
int value, size, cnt;
splay_node *pre, *ch[2];//父亲,双子 


void update() 
{
size = ch[0]->size + ch[1]->size + cnt;
}
//更新元素总数 


//判断它是父亲 得那个孩子 
int get_wh()
{
return pre->ch[0] == this ? 0 : 1;
}
//
void set_ch(int wh, splay_node *child);
} pool[MAX_Q], *root, *null;
//单次节点转换 (儿子,父亲转换) (前做后父亲) 
void splay_node::set_ch(int wh, splay_node *child)
{
ch[wh] = child; 
if (child != null) child->pre = this;
update();//做一次更新一次 
}
//
int top = 0;
//建立新节点 
inline splay_node *get_new(int value)
{
splay_node *now = pool + ++top;//分配内存 
now->value = value;
now->size = 1;          //把自己算进去 
now->cnt = 1;
now->pre = now->ch[0] = now->ch[1] = null;//父亲、孩子也要有null 
return now;
}
//
//旋转大法 
inline void rotate(splay_node *&now)//所在节点也改变 
{
splay_node *old_father = now->pre, 
*grand = now->pre->pre;
int wh = now->get_wh();
old_father->set_ch(wh, now->ch[wh ^ 1]); //父亲做它反儿子的爹换
now->set_ch(wh ^ 1, old_father);//它是它父亲的爹 
now->pre = grand;     //昔日父亲的儿子成为今日爷爷的儿子 
if (grand != null)   //互相认识 
grand->ch[grand->ch[0] == old_father ? 0 : 1] = now;
}
//
//伸展术 
inline void splay(splay_node *now, splay_node *tar)//now是起点,tar是终点 
{
for (; now->pre != tar; rotate(now))//因为不知它的父亲是不是空,所以父亲到目标为止 
if (now->pre->pre != tar)
now->get_wh() == now->pre->get_wh() ? 
rotate(now->pre) : rotate(now);
if (tar == null) root = now;
}
// 
//插入 
void insert(int value) 
{
splay_node *last = null, *now = root;
splay_node *newone = get_new(value);//建节点 
while (now != null)//如果==null就建一个 ,这一步的目的是找位置 
{
last = now;
if (newone->value == now->value)
{
now->cnt++; now->size++;
splay(now, null);//说明有重复,1、+树、2、把now延伸成根 
return;//如果有重复这就完结了 
}
//类似二分查找的东西、、、 
if (newone->value < now->value)
now = now->ch[0];
else
now = now->ch[1];
//
}
//如果只有一个 ,就定根 
if (last == null)
root = newone;
//
else    //到这地步就说明 它正常的进数了 
{
if (newone->value < last->value)
last->set_ch(0, newone);
else
last->set_ch(1, newone);//先把它放进去 


splay(newone, null);//在把它伸展到根 
}
}
//
// 查找 
inline splay_node *find(int value)
{
splay_node *now = root;
// 二分在查找 
while (now != null)
{
if (now->value == value)
break;
if (value < now->value)
now = now->ch[0];
else
now = now->ch[1];
}
//
//固有操作:splay ,有splay!!!!!!! 
if (now != null) splay(now, null);
return now;
}
//
//
inline int pre(int value)
{
int ans = -INF;
splay_node *now = root;
//とある利用搜索树搜索 
while (now != null)
{
if (now->value < value)
{
ans = max(ans, now->value);
now = now->ch[1];
} else
now = now->ch[0];
}
return ans;
}
//
//过程跟上面一模一样 
inline int nxt(int value)
{
int ans = INF;
splay_node *now = root;
while (now != null)
{
if (now->value > value)
{
ans = min(ans, now->value);
now = now->ch[0];
} else
now = now->ch[1];
}
return ans;
}
//
//删除 
void del(int value)
{
splay_node *now = find(value);//用查找 
if (now == null) return;//就没有,清个p 
if (now->cnt > 1)
{
now->cnt--;
now->size--;
return;
}
//善后 
if (now->ch[0] == null && now->ch[1] == null)//没孩子 
root = null;//也就留不下根了 
else if (now->ch[1] == null)//只有左孩子 
{
now->ch[0]->pre = null;
root = now->ch[0];//左孩子当权 
}
else if (now->ch[0] == null)//只有右孩子 
{
now->ch[1]->pre = null;
root = now->ch[1];//右孩子当权 
}
else//两个孩子都有 ,找左的最右 
{
splay_node *_ = now->ch[0];
while (_->ch[1] != null) _ = _->ch[1];
splay(_, now);  //窜到根的左孩子 
_->set_ch(1, now->ch[1]);  //右子树把原来的根夹掉 
_->pre = null;
root = _;
}
}
//
//
inline int get_rank(int value)
{
splay_node *now = root;//依旧从根开始 
int left_size = 0;//用来给右边累加 
while (now != null)
{
if (value == now->value)//找到了 
{
int ans = left_size + now->ch[0]->size + 1;//带上它前期的积累和左边的,不忘加他自己 
splay(now, null);//把它伸展上去 
return ans;
}
if (value < now->value)  //从左边找 
now = now->ch[0];
else
left_size += now->ch[0]->size + now->cnt, now = now->ch[1];//带上左边的和根,向右边找 
}
return -1;
}
//


//排名查找    第k小 
inline int kth(int k)
{
splay_node *now = root;//依旧从根开始 
int left_size = 0;
while (now != null)
{
int _ = left_size + now->ch[0]->size;//左子树是根本 
if (_ + 1 <= k && k <= _ + now->cnt)//找到它了!!! 
{
splay(now, null);//把它放上去 
return now->value;//返回他; 
}
if (k <= _) now = now->ch[0];//往左边找 
else left_size = _ + now->cnt, now = now->ch[1];//加上左边的和根往右找;; 
}
return -1;
}
//
//快读 
inline int get_num()
{
int num = 0;
char c;
bool flag = false;
while ((c = getchar()) == ' ' || c == '\n' || c == '\r');
if (c == '-') flag = true;
else num = c - '0';
while (isdigit(c = getchar()))
num = num * 10 + c - '0';
return (flag ? -1 : 1) * num;
}
//
int main()
{
null = pool;
null->value = 0;
null->size = 0;
null->cnt = 0;
null->pre = null->ch[0] = null->ch[1] = null;
root = null;
    //初始化内存池 
int q = get_num();
//操作数个数 
while (q--)
{
int order = get_num();
//操作个数 
int _ = get_num();
//操作的值 
switch(order)
{
case 1:
insert(_);
break;
case 2:
del(_);
break;
case 3:
printf("%d\n", get_rank(_));
break;
case 4:
printf("%d\n", kth(_));
break;
case 5:
printf("%d\n", pre(_));
break;
case 6:
printf("%d\n", nxt(_));
break;
}
}
}


11、最大流 dinic

#include<iostream>
using namespace std;
#include<cstring>
#include<queue>


const int inf=10005;
struct edge
{int zhi,zhong;
}bian[200001];
queue<int>q;
int tot,hou[200001],xia[10001],deep[10001],s,t,i,j,m,n,yuan[10001],x,y,z;
void addedge(int x,int y,int z)
{
tot++,hou[tot]=yuan[x],yuan[x]=tot,bian[tot].zhong=y,bian[tot].zhi=z;
tot++,hou[tot]=yuan[y],yuan[y]=tot,bian[tot].zhong=x,bian[tot].zhi=0;
}
bool bfs(int s,int t)
{
memset(deep,0x7f,sizeof(deep));

for(i=1;i<=n;i++)
xia[i]=yuan[i];
q.push(s);
deep[s]=0;
while(!q.empty())
   {
    int st=q.front();
    q.pop();
    for(i=xia[st];i!=-1;i=hou[i])
    if(deep[bian[i].zhong]>inf&&bian[i].zhi)
           deep[bian[i].zhong]=deep[st]+1,q.push(bian[i].zhong);
           
  }
return deep[t]<inf;
}

int dfs(int now,int limit)
{
if(!limit||now==t)return limit;
int i,flow=0,f;
for(i=xia[now];i!=-1;i=hou[i])
{
  xia[now]=i;
  if(  deep[bian[i].zhong]==deep[now]+1&&   (f=dfs(bian[i].zhong,min(limit,bian[i].zhi)))     )
  {
  limit-=f;
  flow+=f;
  bian[i].zhi-=f;
  bian[i^1].zhi+=f;
  if(!limit)break;     
  }
}
return flow;
}
int dinic(int s,int t)
{
int daan=0;
while(bfs(s,t))
{
daan+=dfs(s,inf);

}

return daan;
}

int main()
{
tot=-1;
memset(xia,-1,sizeof(xia));
memset(yuan,-1,sizeof(yuan));
cin>>n>>m>>s>>t;
for(i=1;i<=m;i++)
{
cin>>x>>y>>z;
addedge(x,y,z);
}

cout<<dinic(s,t);

}


注意:1、if语句并列前后的位置,需要dfs的放后面!!!!!md坑死了。

2、bfs  注意deep【s】=0!

3、tot初始化-1!!!


声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/知新_RL/article/detail/64594
推荐阅读
相关标签
  

闽ICP备14008679号