AOJ 2313 Box Witch
個人的にハマるポイントが山ほどあったので戒めのメモ。
まず、自分のライブラリはverify済でも信用してはいけません
(まぁこれはverifyした後にちょっとわかり易くしようと書き換えた自分が悪いのでなんとも言えませんが)
(でもまさかadd_edgeが間違ってるとは…)
次に、dfsする前に絶対memset忘れないように!!
(これに大体5時間溶かしました)
そして解法のことですが、辺削除の時どっち向きに流れているか注意!!
(なぜかずっとe.cap>0なら使われててそうでなければ使われてないという判定をしていました)
自分の思考ガバガバすぎなので反省します…
const int MAX_V=100100; struct edge { int to,cap,rev; edge(int to,int cap,int rev):to(to),cap(cap),rev(rev){} }; vector<edge> G[MAX_V]; bool used[MAX_V]; void add_edge(int from,int to,int cap) { edge new_edge1(to,cap,G[to].size()); G[from].pb(new_edge1); edge new_edge2(from,cap,G[from].size()-1); G[to].pb(new_edge2); } 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 flow=0; int N; int max_flow(int s,int t) { for(;;) { memset(used,0,sizeof(used)); int f=dfs(s,t,INF); if(f==0)return flow; flow+=f; } } int ex[505][505]; int E,Q; int ind(int A,int B){for(int i=0;i<G[A].size();i++)if(G[A][i].to==B)return i;} void increase(int A,int B) { int id = ind(A,B); edge &e = G[A][id]; e.cap++; } int decrease(int A,int B) { int id = ind(A,B); edge &e = G[A][id]; int ret = e.cap; e.cap=0; return ret; } int up_query(int A,int B) { increase(A,B); increase(B,A); return max_flow(0,N-1); } int down_query(int A,int B) { int c = decrease(A,B); decrease(B,A); if(c==2)swap(A,B); if(c==1)return flow; else { memset(used,0,sizeof(used)); if(dfs(A,B,1)>0)return flow; memset(used,0,sizeof(used)); dfs(N-1,B,1); memset(used,0,sizeof(used)); dfs(A,0,1); flow--; return flow; } } int main() { scanf("%d %d %d",&N,&E,&Q); for(int i=0;i<E;i++) { int F,T; scanf("%d %d",&F,&T); F--;T--; ex[F][T]=1; ex[T][F]=1; } for(int i=0;i<N;i++) { for(int j=i+1;j<N;j++) { add_edge(i,j,ex[i][j]); } } max_flow(0,N-1); for(int i=0;i<Q;i++) { int M,A,B; scanf("%d %d %d",&M,&A,&B); A--;B--; if(M==1)printf("%d\n",up_query(A,B)); else printf("%d\n",down_query(A,B)); } }