首页 > 代码库 > 图的连通性问题的小结 (双连通、2-SAT)

图的连通性问题的小结 (双连通、2-SAT)

图的连通性问题包括:

1、强连通分量。

2、最小点基和最小权点基。

3、双连通。

4、全局最小割。

5、2-SAT

 

一、强连通分量

强连通分量很少单独出题,一般都是把求强连通分量作为缩点工具。

有三种算法:

1、Kosaraju算法。对原图和反图分别进行一次深度优先搜索。

2、Tarjan算法。用了时间戳。

3、Garbow算法。与Tarjan算法是同一思想,但更精妙。

三种算法的模版我已经贴过了  http://www.cnblogs.com/Potato-lover/p/3956604.html

 

二、最小点基和最小权点基

这个我单独做了总结 http://www.cnblogs.com/Potato-lover/category/606571.html

 

三、双连通

这个也单独做了总结 http://www.cnblogs.com/Potato-lover/p/4001179.html

 

四、全局最小割

学了网络流都知道,最小割问题等价于最大流问题。但是最大流的时间复杂度是O(n*n*n*m), 有时候出题者就要卡时间,最大流算法会超时。

Stoer-Wanger算法

算法的思想是:对于图中的任意两个顶点uv,如果它们属于同一个集合,那么将顶点u和顶点v合并以后并不影响图的最小割。

时间复杂度为O(n*n*n) 

题目:

Hdu 3691 Nubulsa Expo 类似与hdu2914

建图以后直接上模版(主要是要知道有这个算法)

 模版中顶点标号是从0开始的,存图的时候从0开始不用修改模版。题中有重边,重边的处理是把所有的边权值加起来作为一条边。所以矩阵初始化为0。

 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 const int N=1010, INF=0x3f3f3f3f; 7 int Map[N][N],Node[N],dis[N]; 8 bool vis[N]; 9 int ans;10 void SW(int n)11 {12     int maxj,pre,m,i,j;13     ans=INF;14     for(i=0;i<n;i++) Node[i]=i;15     while(n>1)16     {17         m=-1; maxj=1;18         for(i=1;i<n;i++)19         {20             dis[Node[i]]=Map[Node[0]][Node[i]];21             vis[Node[i]]=0;22             if(dis[Node[i]]>m) {m=dis[Node[i]];maxj=i;}23         }24         pre=0;25         vis[Node[0]]=1;26         for(j=1;j<n;j++)27         {28             vis[Node[maxj]]=1;29             if(j==n-1)30             {31                 ans=min(ans,m);32                 for(i=0;i<n;i++)33                 {34                     Map[Node[pre]][Node[i]]+= Map[Node[maxj]][Node[i]];35                     Map[Node[i]][Node[pre]]+= Map[Node[maxj]][Node[i]];36                 }37                 Node[maxj]=Node[--n];38             }39             else40             {41                 pre=maxj; m=-1;42                 for(i=1;i<n;i++)43                 {44                     if(!vis[Node[i]])45                     {46                         dis[Node[i]] += Map[Node[pre]][Node[i]];47                         if(dis[Node[i]]>m) {m=dis[Node[i]]; maxj=i;}48                     }49                 }50             }51         }52     }53 }54 int main()55 {56     freopen("test.txt","r",stdin);57     int n,m,s,i,j,k;58     while(scanf("%d%d%d",&n,&m,&s)!=EOF&&n)59     {60         memset(Map,0,sizeof(Map));61         while(m--)62         {63             scanf("%d%d%d",&i,&j,&k);64             i--;j--;65             Map[i][j]+=k; Map[j][i]+=k;66         }67         SW(n);68         printf("%d\n",ans);69     }70     return 0;71 }
View Code

 

五、2-SAT

以前做出总结  http://www.cnblogs.com/Potato-lover/p/3965512.html

 

PS:参考资料主要来自《图论及应用》,哈尔冰工业大学出版。

 

图的连通性问题的小结 (双连通、2-SAT)