[POJ1815] 网络流、求最小点割

【题目大意】给你N个点，源点和汇点，然后给定一个邻接矩阵，让你求从源到汇的一个字典序最小的点割集。

【算法分析】一个点拆成两个点，图中的边设成0x7FFFFFFF，然后一个点管出度，一个点管入度。然后就变成了求这个网络的最小割。由于题目要求字典序最小，所以必须枚举删点。

【其他】WA了1次，因为NO ANSWER的其中一个情况漏掉了。
6390962 edward2 1815 Accepted 864K 579MS G++ 2568B 2010-01-30 23:22:14
【CODE】
#include #include #include #define E 100000
#define N 401
struct edge{int x,y,op,c,next;}g[E];
int n,S,T,e,a[N][N];
int fa[N],cur[N],num[N],d[N],ls[N],v[N];

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

int change(){
int nf=0x7FFFFFFF;
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;
}
return nf;
}

int sap(){
int FF=0;
memset(d,0,sizeof(d));
memset(num,0,sizeof(num));
for (int i=1;i<=2*n;i++) cur[i]=ls[i];
num[0]=2*n;
int i=S;
while (d[S]<2*n){
for (;cur[i]!=0;cur[i]=g[cur[i]].next)
if (g[cur[i]].c>0 && d[g[cur[i]].y]+1==d[i]) break;
if (cur[i]==0){
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){
FF+=change();
i=S;
}
}
}
return FF;
}

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;
}

void init(){
memset(v,0,sizeof(v));
scanf("%d%d%d",&n,&S,&T);
S+=n;
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
scanf("%d",&a[i][j]);
}

void work(){
if (S-n==T || a[S-n][T]==1){
printf("NO ANSWER!n");
return;
}
e=0; memset(ls,0,sizeof(ls));
for (int i=1;i<=n;i++) addedge(i,i+n,1);
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
if (a[i][j]) addedge(i+n,j,0x7FFFFFFF);
int flow=sap();
printf("%dn",flow);
for (int i=1;i<=n;i++){
if (flow==0) break;
v[i]=1;
e=0; memset(ls,0,sizeof(ls));
for (int j=1;j<=n;j++)
if (v[j]==0) addedge(j,j+n,1);
for (int j=1;j<=n;j++)
for (int k=1;k<=n;k++)
if (a[j][k]) addedge(j+n,k,0x7FFFFFFF);
int tf=sap();
if (tf else v[i]=0;
}
for (int i=1;i<=n;i++)
if (v[i]) printf("%d ",i);
}

int main(){
init();
work();
}