[POJ 1966] 网络流、求无向图的点连通度

【题目大意】给定一个无向图，让你求最小去掉多少个点以后使得原图不连通。

【算法分析】如果是有源汇的话就简单了，直接拆点然后求最小割就可以。于是这题就枚举源汇求最小割就行了。

【其它】1A
6393220 edward2 1966 Accepted 396K 125MS G++ 2212B 2010-01-31 18:25:01
【CODE】
#include #include #include #define inf 200
struct gtp{int x,y,next,c,op;}g[10000];
int n,m,e,a[50][50],S,T,flow;
int ls[100],cur[100],fa[100],d[100],num[100];

void relabel(int k){
int mm=n+n;
cur[k]=ls[k];
for (int t=ls[k];t!=0;t=g[t].next)
if (g[t].c && d[g[t].y] d[k]=mm+1;
}

void change(){
int nf=inf;
for (int i=T;i!=S;i=g[fa[i]].x)
if (g[fa[i]].c for (int i=T;i!=S;i=g[fa[i]].x){
g[fa[i]].c-=nf;
g[g[fa[i]].op].c+=nf;
}
flow+=nf;
}

void sap(){
flow=0;
memset(d,0,sizeof(d));
memset(num,0,sizeof(num));
for (int i=0;i num[0]=n+n;
int i=S;
while (d[0] for (;cur[i]!=0;cur[i]=g[cur[i]].next)
if (g[cur[i]].c && d[g[cur[i]].y]+1==d[i]) break;
if (!cur[i]){
if (–num[d[i]]==0) break;
relabel(i);
num[d[i]]++;
if (i!=S) i=g[fa[i]].x;
}
else{
fa[g[cur[i]].y]=cur[i];
i=g[cur[i]].y;
if (i==T){
change();
i=S;
}
}
}
}

inline void addedge(int x,int y,int c){
e++;
g[e].x=x; g[e].y=y; g[e].c=c; g[e].op=e+1; g[e].next=ls[x]; ls[x]=e;
e++;
g[e].x=y; g[e].y=x; g[e].c=0; g[e].op=e-1; g[e].next=ls[y]; ls[y]=e;
}

int main(){
while (scanf("%d%d",&n,&m)!=EOF){
memset(a,0,sizeof(a));
for (int i=1;i<=m;i++){
int x,y;
scanf(" (%d,%d)",&x,&y);
a[x][y]=1; a[y][x]=1;
}
int ans=inf;
for (S=n;S<2*n;S++)
for (T=0;T if (S-n!=T){
e=0;
memset(ls,0,sizeof(ls));
for (int i=0;i for (int j=0;j if (a[i][j]) addedge(i+n,j,inf);
for (int i=0;i sap();
if (flow }
if (ans>n) ans=n;
printf("%dn",ans);
}
return 0;
}