Cable TV Network Time Limit: 3000MS 64bit IO Format: %lld & %llu
求无向图的点连通度，也就是说求任意两点最小割的最小值。 但是考虑S集合和T集合，中间由若干条边连接，这些边就是S到T的最小割，假设这种情况是答案，那么发现其实不需要枚举所有的点，而是固定一个点，枚举另一个点就可以保证有至少一种情况是一点在S集合另一点在T集合里。 然后由于一个点只能经过一次，那么拆点之后连接容量为1的边，然后其他边连成INF。 注意每次都要把源点和汇点容量生成INF，表示不能切这条边。 论文中还提到另外的方法，可以求出原图的最小生成树再来求解，对于这道题来说没有必要。 下面是枚举所有点对的代码：
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<cmath> #include<vector> #include<queue> #include<stack> #include<map> #include<string> #include<iomanip> #include<ctime> #include<climits> #include<cctype> #include<algorithm> using namespace std; inline int read(int &x) { x=0; char ch='\0';int flag=1; while(ch<'0'||ch>'9') { ch=getchar(); if(ch==EOF) return -1; if(ch=='-') { flag=-1;ch=getchar();break; } } while(ch>='0'&&ch<='9') { x*=10; x+=ch-'0'; ch=getchar(); } x*=flag; return 1; } const int INF=0x3f3f3f3f; const int maxn=50+5; struct Edge { int to,next; int cap; }edge0[maxn*maxn<<2],edge[maxn*maxn<<2]; int head[maxn<<1]; int maxedge0; inline void addedge(int u,int v,int cap) { edge0[++maxedge0]=(Edge){v,head[u],cap}; head[u]=maxedge0; edge0[++maxedge0]=(Edge){u,head[v],0}; head[v]=maxedge0; } int n,m; bool Zero; inline bool init() { if(!~read(n)||!~read(m)) return false; if((n==0||n==1)&&m==0) { printf("%d\n",n);Zero=true;return true; } memset(head,-1,sizeof(head)); maxedge0=-1; for(int i=1;i<=n;i++) addedge(i,i+n,1); for(int i=1;i<=m;i++) { int a,b; read(a),read(b); a++,b++; addedge(a+n,b,INF); addedge(b+n,a,INF); } return true; } int d[maxn<<1],cur[maxn<<1]; bool vis[maxn<<1]; inline bool bfs(int S,int T) { queue <int> que; memset(vis,false,sizeof(vis)); vis[S]=true;d[S]=1;que.push(S); while(!que.empty()) { int u=que.front();que.pop(); for(int i=head[u];~i;i=edge[i].next) { if(!edge[i].cap) continue;//both cap>0 and non_visited!!! int v=edge[i].to; if(vis[v]) continue; d[v]=d[u]+1; if(v==T) return true; que.push(v),vis[v]=true; } } return false; } int dfs(int u,int T,int minflow) { if(u==T||minflow==0) return minflow; int flow=0; for(int &i=cur[u];~i;i=edge[i].next) { int v=edge[i].to,f; if(d[v]==d[u]+1&&(f=dfs(v,T,min(minflow,edge[i].cap)))) { edge[i].cap-=f; edge[i^1].cap+=f; flow+=f; minflow-=f; if(!minflow) return flow; } } return flow; } inline int dinic(int S,int T) { int ret=0; while(bfs(S,T)) { memcpy(cur,head,sizeof(head)); ret+=dfs(S,T,INF); } return ret; } inline void edgecpy() { for(int k=0;k<=maxedge0;k++) edge[k]=edge0[k]; } inline void expand(int x) { edge[(x<<1)-2].cap=INF; } inline int work() { int ret=n; for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) { edgecpy(); expand(i);expand(j); int tmp=dinic(i,j+n);//from the inside vertex if(ret>tmp) ret=tmp; } return ret; } int main() { freopen("tv.in","r",stdin); freopen("tv.out","w",stdout); while(init()) { if(Zero) { Zero=false;continue; } printf("%d\n",work()); } return 0; }