AOJ 2594 : Reverse a Road II
問題リンク : Reverse a Road II | Aizu Online Judge
問題概要 :
V個のノードとE本の有向辺からなるグラフがある
それぞれのノードには1から順に番号が割り振られており、
S番からT番に車をできるだけ多くの車を送る
ただし、1つの辺を通れる車は高々1台
あなたは1本だけ辺の向きを逆転させることができる
これによってSからTへ送れる車の数を初期状態より多くできるか?
できるのであれば逆転した後に送れる車の最大数とそのような辺の数を出力せよ
そうでないばあいは初期状態における車の最大数と0を出力せよ
解法 :
以下は自分用備忘録
最大流なのだが、それはそうなのだが、
詳しくは公式の解説にあるとうりなので、、
一瞬なんで残余グラフでなんだと思ったのでその理由だけメモ
深夜にやっているのが悪かったのかな、そら残余グラフでしょう
残余グラフを使って到達できる場所から辺を反転させてTまで到達できるのであれば、
その通りにフロー流せるでしょ
打ち消しあって、その辺を使わないでながせるでしょう
なんで残余なのかわからなかったのか、謎だが後でまた同じように悩むことがないように、備忘録
コード :
#include<bits/stdc++.h> #define REP(i,s,n) for(int i=s;i<n;i++) #define rep(i,n) REP(i,0,n) using namespace std; const int MAX_V = 3000; const int IINF = INT_MAX; typedef pair<int,int> ii; map<ii,int> mp; ///////// struct Edge{ int to,cap,rev; bool isRev; }; vector<Edge> G[MAX_V]; bool used[MAX_V]; void add_edge(int from,int to,int cap){ G[from].push_back((Edge){to,cap,G[to].size(),false}); G[to].push_back((Edge){from,0,G[from].size()-1,true}); } int dfs(int v,int t,int f){ if( v == t ) return f; used[v] = true; for(int i=0;i<G[v].size();i++){ Edge &e = G[v][i]; if( !used[e.to] && e.cap > 0 ){ int d = dfs(e.to,t,min(f,e.cap)); if( d > 0 ){ e.cap -= d; G[e.to][e.rev].cap += d; return d; } } } return 0; } int max_flow(int s,int t){ int flow = 0; for(;;){ memset(used,0,sizeof(used)); int f = dfs(s,t,IINF); if( f == 0 ) return flow; flow += f; } } vector<int> G2[MAX_V],rG2[MAX_V]; bool visited[2][MAX_V]; void init(int _size=MAX_V){ rep(i,_size) G[i].clear(), G2[i].clear(), rG2[i].clear(); } int V,E; void icompute(int s,bool used[MAX_V],int type){ used[s] = true; deque<int> deq; deq.push_back(s); while( !deq.empty() ){ int cur = deq.front(); deq.pop_front(); rep(i,(int)(type?G2[cur].size():rG2[cur].size())){ int next = type?G2[cur][i]:rG2[cur][i]; if( !used[next] ) { used[next] = true; deq.push_back(next); } } } } void compute(int let,int go){ int maxi = max_flow(let,go); rep(i,V) { int s = i; rep(j,(int)G[i].size()) if( G[i][j].cap ) { int t = G[i][j].to, c = G[i][j].cap; G2[s].push_back(t), rG2[t].push_back(s); } } memset(visited,false,sizeof(visited)); icompute(let,visited[0],1); icompute(go ,visited[1],0); /* rep(i,V) { cout << i+1 << "-th : " << visited[0][i] << " "; } cout << endl << endl; rep(i,V) { cout << i+1 << "-th : " << visited[1][i] << " "; } cout << endl << endl; */ int cnt = 0; rep(i,V) rep(j,(int)G[i].size()) if( G[i][j].cap && !G[i][j].isRev ) { if( visited[0][G[i][j].to] && visited[1][i] ) ++cnt; } cout << maxi + ( cnt > 0 ) << " " << cnt << endl; } int main(){ int s,t; while( cin >> V >> E >> s >> t, V|E|s|t ) { --s, --t; init(V); set<ii> S; rep(i,E) { int a,b; scanf("%d %d",&a,&b); --a, --b; add_edge(a,b,1); } compute(s,t); } return 0; }