某岛

… : "…アッカリ～ン . .. . " .. .
September 14, 2010

BZOJ 1797. [Ahoi2009]Mincut 最小割

Analyse :

Orz hf46中 MSK 神牛的题。。。

```/*
Author  : xiaodao
Problem : AHOI 2009 Mincut 最小割
Status  : Accepted
Last Modify : GMT +8. Sept 14th 08:12.
Tags : 网络流，最小割，强连通分量
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <cmath>

using namespace std;
const int INF = 0x7fffffff;
const int N = 40100, M = 123001;
struct edge{
int v, c;
void insert(int, int);
};
struct node{
int D, scc;
};
struct network_flow{
node V[N+1]; edge E[M+1];
int edge_count; int max_flow;
int n, m, s, t;
bool C[N+1]; int F[N+1] ,time;
int component;

void init();
void print();
void bfs(); void dfs1(int); void dfs2(int);
void Dinitz();
void Kosaraju();
};
inline int _r(int x){
return x ^ 1;
}
void edge::insert(int a, int b){
v = a; c = b;
};
void network_flow::add_edge(int x, int y, int z){
}

void network_flow::bfs(){
int Q[N+1] = {s}, head = 0, tail = 1;
for (int i=1;i<=n;i++) V[i].D = -1;
V[s].D = 0;

int u;
if (V[arc.v].D==-1 && arc.c>0){
Q[tail] = arc.v; V[arc.v].D = V[u].D + 1;
if (arc.v == t) return;
tail++;
}
}
}
}

void network_flow::Dinitz(){
max_flow = 0;

bfs();
while (V[t].D!=-1){
int stack[n+1], cur[n+1], top = 0;
memset(cur, 0, sizeof(cur));
stack[0] = M;

int u; size_t i;
while (top!=-1){
u = E[stack[top]].v;
if (u == t){
int delta = INF; int handle;
for (int i=1;i<=top;i++){
edge &arc = E[stack[i]];
if (arc.c < delta){
delta = arc.c;
handle = i;
}
}
max_flow += delta;
for (int i=1;i<=top;i++){
E[stack[i]].c -= delta;
E[_r(stack[i])].c += delta;
}

//for (int i=handle;i<=top;i++){
//  cur[stack[i]] = 0;
//}  // ?

top = handle-1;
continue;
}

if (V[arc.v].D == V[u].D + 1 && arc.c>0) break;
}

V[u].D = -1, top--;
}
else {
cur[u] = i + 1;
}
}
bfs();
}
}

void network_flow::dfs1(int u){
C[u] = true;
if (!C[arc.v] && arc.c!=0)
dfs1(arc.v);
}
F[time++] = u;
}

void network_flow::dfs2(int u){
C[u] = true; V[u].scc = component;
if (!C[arc.v] && rev_arc.c!=0)
dfs2(arc.v);
}
}

void network_flow::Kosaraju(){
memset(C, false , sizeof(C)); time = 0;
for (int i=1;i<=n;i++)
if (!C[i]) dfs1(i);

memset(C, false, sizeof(C));
component = 0;
for (int i=n-1;i>=0;i--)
if (!C[F[i]]) dfs2(F[i]), component++;
}

void network_flow::init(){
edge_count = 0; E[M].v = s;

int x, y, z;
for (int i=0;i<m;i++){
scanf("%d%d%d", &x, &y, &z);
}
}

void network_flow::print(){
for (int i=0;i<m;i++)
if (E[2*i].c !=0 || V[E[2*i+1].v].scc == V[E[2*i].v].scc) printf("0 0\n");
else {
if (V[E[2*i+1].v].scc != V[s].scc || V[E[2*i].v].scc != V[t].scc)  printf("1 0\n");
else printf("1 1\n");
}
}

network_flow G;

int main(){
//freopen("in.txt", "r", stdin);
while (scanf("%d%d%d%d", &G.n, &G.m, &G.s, &G.t)==4){
G.init(); G.Dinitz(); G.Kosaraju();
G.print();
}
}
```