\u5224\u65ad\u6d41\u7f51\u7edc\u7684\u8fb9\u96c6\uff0c\u5728\u6700\u5c0f\u5272\u4e2d\uff0c\u662f\u5426\u6709\u53ef\u80fd\u6210\u4e3a\u5272\u8fb9\u7684\uff1f\u662f\u5426\u4e00\u5b9a\u4f1a\u6210\u4e3a\u5272\u8fb9\uff1f
\n<\/p>\n
Orz hf46\u4e2d MSK \u795e\u725b\u7684\u9898\u3002\u3002\u3002
\nhttp:\/\/hi.baidu.com\/matrush\/blog\/item\/091adb03b4eedd0d728da54c.html<\/p>\n
\n\/*\n Author : xiaodao\n Problem : AHOI 2009 Mincut \u6700\u5c0f\u5272\n Status : Accepted\n Last Modify : GMT +8. Sept 14th 08:12.\n Tags : \u7f51\u7edc\u6d41\uff0c\u6700\u5c0f\u5272\uff0c\u5f3a\u8fde\u901a\u5206\u91cf\n*\/\n#include <iostream>\n#include <cstdio>\n#include <cstring>\n#include <vector>\n#include <cmath>\n\nusing namespace std;\nconst int INF = 0x7fffffff;\nconst int N = 40100, M = 123001;\nstruct edge{\n int v, c;\n void insert(int, int);\n};\nstruct node{\n vector<int> adj;\n int D, scc;\n};\nstruct network_flow{\n node V[N+1]; edge E[M+1];\n int edge_count; int max_flow;\n int n, m, s, t;\n bool C[N+1]; int F[N+1] ,time;\n int component;\n\n void init();\n void print();\n void add_edge(int, int, int);\n void bfs(); void dfs1(int); void dfs2(int);\n void Dinitz();\n void Kosaraju();\n};\ninline int _r(int x){\n return x ^ 1;\n}\nvoid edge::insert(int a, int b){\n v = a; c = b;\n};\nvoid network_flow::add_edge(int x, int y, int z){\n V[x].adj.push_back(edge_count); E[edge_count++].insert(y, z);\n}\n\n\nvoid network_flow::bfs(){\n int Q[N+1] = {s}, head = 0, tail = 1;\n for (int i=1;i<=n;i++) V[i].D = -1;\n V[s].D = 0;\n\n int u;\n while (head<tail){\n u = Q[head];\n for (size_t i=0;i<V[u].adj.size();i++){\n edge &arc = E[V[u].adj[i]];\n if (V[arc.v].D==-1 && arc.c>0){\n Q[tail] = arc.v; V[arc.v].D = V[u].D + 1;\n if (arc.v == t) return;\n tail++;\n }\n }\n head++;\n }\n}\n\nvoid network_flow::Dinitz(){\n max_flow = 0;\n\n bfs();\n while (V[t].D!=-1){\n int stack[n+1], cur[n+1], top = 0;\n memset(cur, 0, sizeof(cur));\n stack[0] = M;\n\n int u; size_t i;\n while (top!=-1){\n u = E[stack[top]].v;\n if (u == t){\n int delta = INF; int handle;\n for (int i=1;i<=top;i++){\n edge &arc = E[stack[i]];\n if (arc.c < delta){\n delta = arc.c;\n handle = i;\n }\n }\n max_flow += delta;\n for (int i=1;i<=top;i++){\n E[stack[i]].c -= delta;\n E[_r(stack[i])].c += delta;\n }\n\n \/\/for (int i=handle;i<=top;i++){\n \/\/ cur[stack[i]] = 0;\n \/\/} \/\/ ?\n\n top = handle-1;\n continue;\n }\n\n for (i=cur[u];i<V[u].adj.size();i++){\n edge &arc = E[V[u].adj[i]];\n if (V[arc.v].D == V[u].D + 1 && arc.c>0) break;\n }\n\n if (i == V[u].adj.size()){\n V[u].D = -1, top--;\n }\n else {\n cur[u] = i + 1;\n stack[++top] = V[u].adj[i];\n }\n }\n bfs();\n }\n}\n\n\n\nvoid network_flow::dfs1(int u){\n C[u] = true;\n for (int i=0;i<V[u].adj.size();i++){\n edge &arc = E[V[u].adj[i]];\n if (!C[arc.v] && arc.c!=0)\n dfs1(arc.v);\n }\n F[time++] = u;\n}\n\nvoid network_flow::dfs2(int u){\n C[u] = true; V[u].scc = component;\n for (int i=0;i<V[u].adj.size();i++){\n edge &rev_arc = E[_r(V[u].adj[i])];\n edge &arc = E[V[u].adj[i]];\n if (!C[arc.v] && rev_arc.c!=0)\n dfs2(arc.v);\n }\n}\n\n\nvoid network_flow::Kosaraju(){\n memset(C, false , sizeof(C)); time = 0;\n for (int i=1;i<=n;i++)\n if (!C[i]) dfs1(i);\n\n memset(C, false, sizeof(C));\n component = 0;\n for (int i=n-1;i>=0;i--)\n if (!C[F[i]]) dfs2(F[i]), component++;\n}\n\n\n\nvoid network_flow::init(){\n for (int i=1;i<=n;i++) V[i].adj.clear();\n edge_count = 0; E[M].v = s;\n\n int x, y, z;\n for (int i=0;i<m;i++){\n scanf("%d%d%d", &x, &y, &z);\n add_edge(x, y, z);\n add_edge(y, x, 0);\n }\n}\n\nvoid network_flow::print(){\n for (int i=0;i<m;i++)\n if (E[2*i].c !=0 || V[E[2*i+1].v].scc == V[E[2*i].v].scc) printf("0 0\\n");\n else {\n if (V[E[2*i+1].v].scc != V[s].scc || V[E[2*i].v].scc != V[t].scc) printf("1 0\\n");\n else printf("1 1\\n");\n }\n}\n\n\nnetwork_flow G;\n\nint main(){\n \/\/freopen("in.txt", "r", stdin);\n while (scanf("%d%d%d%d", &G.n, &G.m, &G.s, &G.t)==4){\n G.init(); G.Dinitz(); G.Kosaraju();\n G.print();\n }\n}\n<\/pre>\n