本文共 1349 字，大约阅读时间需要 4 分钟。
求一个图的联通度，就是找图中固定源点，然后枚举汇点求最小割。
然后最小割中最小的一个就是图的联通度。
#include #include #include #include #include #include #define MM(x,y) memset(x,y,sizeof(x))#define INF 0x3f3f3f3f#define LL long longusing namespace std;/* ShellDawn POJ1966 No.36 */#define maxn 55int N,M;int S,T;struct Edge{ int to; int v; int rvs; int pre;};Edge E[maxn*maxn*4];int pre[maxn*2];int cnt;int In[maxn*maxn][2];int V[maxn*2];void addE(int a,int b,int v){ E[cnt].to = b; E[cnt].v = v; E[cnt].rvs = cnt+1; E[cnt].pre = pre[a]; pre[a] = cnt++; E[cnt].to = a; E[cnt].v = 0; E[cnt].rvs = cnt - 1; E[cnt].pre = pre[b]; pre[b] = cnt ++;}bool BFS(int s){ MM(V,0); queue q; q.push(s); V[s] = 1; while(!q.empty()){ int now = q.front(); q.pop(); for(int i=pre[now];i!=0;i=E[i].pre){ if(E[i].v > 0 && V[E[i].to] == 0){ V[E[i].to] = V[now] + 1; q.push(E[i].to); } } } if(V[T] > 0) return true; return false;}int DFS(int now,int minflow){ if(now == T) return minflow; int flow = 0; for(int i=pre[now];i!=0 && minflow; i = E[i].pre){ if(E[i].v > 0 && V[E[i].to] == V[now] + 1){ int f = DFS(E[i].to,min(minflow,E[i].v)); flow += f; minflow -= f; E[i].v -= f; E[E[i].rvs].v += f; } } if(flow == 0) V[now] = 0; return flow;}void build(){ MM(pre,0); cnt = 1; for(int i=0;i 1){printf("0\n");continue;} for(int i=0;i =INF?N:ans); } return 0;}
转载地址：http://tnwji.baihongyu.com/