图的连通性问题的小结（双连通、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算法：

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

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

题目：

Hdu 3691 Nubulsa Expo 类似与hdu2914

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

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

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 const int N=, INF=0x3f3f3f3f;

 int Map[N][N],Node[N],dis[N];

 bool vis[N];

 int ans;

 void SW(int n)

 {

     int maxj,pre,m,i,j;

     ans=INF;

     for(i=;i<n;i++) Node[i]=i;

     while(n>)

     {

         m=-; maxj=;

         for(i=;i<n;i++)

         {

             dis[Node[i]]=Map[Node[]][Node[i]];

             vis[Node[i]]=;

             if(dis[Node[i]]>m) {m=dis[Node[i]];maxj=i;}

         }

         pre=;

         vis[Node[]]=;

         for(j=;j<n;j++)

         {

             vis[Node[maxj]]=;

             if(j==n-)

             {

                 ans=min(ans,m);

                 for(i=;i<n;i++)

                 {

                     Map[Node[pre]][Node[i]]+= Map[Node[maxj]][Node[i]];

                     Map[Node[i]][Node[pre]]+= Map[Node[maxj]][Node[i]];

                 }

                 Node[maxj]=Node[--n];

             }

             else

             {

                 pre=maxj; m=-;

                 for(i=;i<n;i++)

                 {

                     if(!vis[Node[i]])

                     {

                         dis[Node[i]] += Map[Node[pre]][Node[i]];

                         if(dis[Node[i]]>m) {m=dis[Node[i]]; maxj=i;}

                     }

                 }

             }

         }

     }

 }

 int main()

 {

     freopen("test.txt","r",stdin);

     int n,m,s,i,j,k;

     while(scanf("%d%d%d",&n,&m,&s)!=EOF&&n)

     {

         memset(Map,,sizeof(Map));

         while(m--)

         {

             scanf("%d%d%d",&i,&j,&k);

             i--;j--;

             Map[i][j]+=k; Map[j][i]+=k;

         }

         SW(n);

         printf("%d\n",ans);

     }

     return ;

 }

五、2-SAT

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

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

巴特西

图的连通性问题的小结（双连通、2-SAT）

最新文章

热门文章

巴特西

图的连通性问题的小结 （双连通、2-SAT）

最新文章

热门文章

图的连通性问题的小结（双连通、2-SAT）