Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
哪位大牛路过帮忙看看,指点一下吧,狂wa-ing#include<iostream> #include<string.h> #include<stdio.h> using namespace std; const int Max=404; const int INF=1<<30; int map[Max][Max],c[Max][Max]; int ans[Max]; int queue[Max],pre[Max]; void built_Graph(int n) { memset(map,0,sizeof(map)); for(int i=1;i<=n;i++) { map[i*2-1][i*2]=map[i*2][i*2-1]=1; for(int j=1;j<=n;j++) if(c[i][j]) map[i*2][j*2]=INF; } } int bfs(int s,int t,int n) { int head=0,tail=0; queue[tail++]=s; //cout<<"queue "<<queue[head]<<endl; memset(pre,-1,sizeof(pre)); while(head<tail) { int u=queue[head++]; // cout<<"queue "<<u<<endl; for(int i=1;i<=n;i++) { // cout<<u<<" "<<i<<" "<<c[u][i]<<" pre "<<pre[i]<<endl; if(c[u][i]>0&&pre[i]==-1) { queue[tail++]=i; // cout<<i<<endl; pre[i]=u; if(i==t) break; } } } if(pre[t]==-1) return 0; int delta=INF; for(int i=t;i!=s;i=pre[i]) delta=min(delta,c[pre[i]][i]); if(delta==INF) return 0; else return delta; } int max_flow(int s,int t,int n) { int flow=0; while(1) { int delta=bfs(s,t,n); //cout<<delta<<endl; if(delta==0) break; flow+=delta; for(int i=t;i!=s;i=pre[i]) { //cout<<i<<" "; c[pre[i]][i]-=delta; c[i][pre[i]]+=delta; }//cout<<endl; } return flow; } int main() { int n,s,t; while(scanf("%d%d%d",&n,&s,&t)!=EOF) { memset(ans,0,sizeof(ans)); memset(c,0,sizeof(c)); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%d",&c[i][j]); if(c[s][t]) { printf("NO ANSWER!\n"); continue; } built_Graph(n); memcpy(c,map,sizeof(map)); int F=max_flow(s,t,2*n); //cout<<"flow "<<F<<endl; int num=0; for(int i=1;i<=n;i++) if(i!=s&&i!=t) { memcpy(c,map,sizeof(map)); c[i*2-1][i*2]=c[i*2][i*2-1]=0; int temp; if((temp=max_flow(s,t,2*n))!=F) { //cout<<"flow "<<temp<<endl; map[i*2-1][i*2]=map[i*2][i*2-1]=0; ans[++num]=i; F--; } } if(num==0) { printf("%d\n",0); continue; } printf("%d\n",num); for(int i=1;i<=num;i++) { if(i>1) printf(" "); printf("%d",ans[i]); } printf("\n"); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator