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