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

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！！！