残余グラフとか最小カットとかを真面目に考察しないといけない。かなり難しいと思う…。
#include<stdio.h> #include<algorithm> #include<vector> #include<map> #include<queue> using namespace std; const int D_MAX_V=2002; const int D_v_size=2002; struct D_wolf{ int t,c,r; D_wolf(){t=c=r=0;} D_wolf(int t1,int c1,int r1){ t=t1;c=c1;r=r1; } }; vector<D_wolf>D_G[D_MAX_V]; int D_level[D_MAX_V]; int D_iter[D_MAX_V]; void add_edge(int from,int to,int cap){ /* for(int i=0;i<D_G[from].size();i++){ if(to==D_G[from][i].t){ D_G[from][i].c+=cap; return; } }*/ D_G[from].push_back(D_wolf(to,cap,D_G[to].size())); D_G[to].push_back(D_wolf(from,0,D_G[from].size()-1)); } void D_bfs(int s){ for(int i=0;i<D_v_size;i++)D_level[i]=-1; queue<int> Q; D_level[s]=0; Q.push(s); while(Q.size()){ int v=Q.front(); Q.pop(); for(int i=0;i<D_G[v].size();i++){ if(D_G[v][i].c>0&&D_level[D_G[v][i].t]<0){ D_level[D_G[v][i].t]=D_level[v]+1; Q.push(D_G[v][i].t); } } } } int D_dfs(int v,int t,int f){ if(v==t)return f; for(;D_iter[v]<D_G[v].size();D_iter[v]++){ int i=D_iter[v]; if(D_G[v][i].c>0&&D_level[v]<D_level[D_G[v][i].t]){ int d=D_dfs(D_G[v][i].t,t,min(f,D_G[v][i].c)); if(d>0){ D_G[v][i].c-=d; D_G[D_G[v][i].t][D_G[v][i].r].c+=d; return d; } } } return 0; } int max_flow(int s,int t){ int flow=0; for(;;){ D_bfs(s); if(D_level[t]<0)return flow; for(int i=0;i<D_v_size;i++)D_iter[i]=0; int f; while((f=D_dfs(s,t,99999999))>0){flow+=f;} } return 0; } int c,d; int x[1100]; int y[1100]; int N; int p[11000]; int q[11000]; int at[11000]; int main(){ int a,b; while(scanf("%d%d%d%d",&a,&b,&c,&d),a){ c--;d--; N=a; for(int i=0;i<2002;i++){ D_G[i].clear(); D_level[i]=D_iter[i]=0; } for(int i=0;i<b;i++){ scanf("%d%d",p+i,q+i); p[i]--;q[i]--; at[i]=D_G[p[i]].size(); add_edge(p[i],q[i],1); } int v=max_flow(c,d); queue<int>Q; for(int i=0;i<a;i++)x[i]=y[i]=0; x[c]=1; Q.push(c); while(Q.size()){ int now=Q.front();Q.pop(); for(int i=0;i<D_G[now].size();i++){ if(!x[D_G[now][i].t]&&D_G[now][i].c){ x[D_G[now][i].t]=1; Q.push(D_G[now][i].t); } } } y[d]=1; Q.push(d); while(Q.size()){ int now=Q.front();Q.pop(); for(int i=0;i<D_G[now].size();i++){ if(!y[D_G[now][i].t]&&D_G[D_G[now][i].t][D_G[now][i].r].c){ y[D_G[now][i].t]=1; Q.push(D_G[now][i].t); } } } int ret=0; for(int i=0;i<b;i++){ if(D_G[p[i]][at[i]].c==0)continue; if(x[q[i]]&&y[p[i]])ret++; } if(ret==0)printf("%d %d\n",v,ret); else printf("%d %d\n",v+1,ret); } }