### Brief description :

給定一張分層圖，求一次阻塞流…

### Analyse :

… 我還有東西需要確認。

```
/*
Author: xiaodao
Prog: ZOJ 2364 / SGU 212. Data Transmission
Status: Labeled
Last modify: GMT +8 Aug 22th 01:52
Tags: Network_flow
*/
#include
```
#include
#include
#include
using namespace std;
const int INF = 0x7fffffff;
const int N = 1500, M = 300000 * 2;
struct edge{
int v, c;
void insert(int, int);
} E[M+1]; int edge_count;
vector adj[N+1], reverse_adj[N+1]; int D[N+1];
int n, m, l, s, t;
int _r(int x){
return x ^ 1;
}
void edge::insert(int a, int b){
v = a; c = b;
}
void add_edge(int x, int y, int c){
adj[x].push_back(edge_count); E[edge_count++].insert(y, c);
}
void add_reverse_edge(int x, int y, int c){
reverse_adj[x].push_back(edge_count); E[edge_count++].insert(y, c);
}
void Dinitz(){
//bfs();
//while (D[t]!=-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;
//cout << u << endl;
if (u == t){
int handle = 1;
for (int i=2;i<=top;i++)
if (E[stack[i]].c < E[stack[handle]].c)
handle = i;
int delta = E[stack[handle]].c;
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[E[stack[i]].v] = 0; // ###
top = handle - 1;
continue;
}
for (i=cur[u];i layer[N+1];
long long excess[N+1];
cin >> n >> m >> l;
edge_count = 0;
for (int i=1;i<=n;i++)
adj[i].clear(), reverse_adj[i].clear();
for (int i=1;i<=l;i++)
layer[i].clear();
for (int i=1;i<=n;i++){
scanf("%d", &D[i]); layer[D[i]].push_back(i);
if (D[i] == 1) s = i;
else if (D[i] == l) t = i;
}
int x, y, c;
for (int i=1;i<=m;i++){
scanf("%d%d%d", &x, &y, &c);
add_edge(x, y, c);
add_reverse_edge(y, x, 0);
}
E[M].v = s; // ~
/* 我是貪心初始流。。。 */
/* 步驟一：灌水 */
memset(excess, 0, sizeof(excess));
//excess[s] = INF;
excess[s] = ((long long)1 << 63 ) - 1;
for (int i=1;i=2;i--){
for (size_t j=0;j 0){
for (size_t k=0;k= 0){
rev.c += excess[u]; arc.c -= excess[u];
excess[arc.v] += excess[u]; excess[u] = 0;
break;
}
else {
excess[u] -= arc.c; excess[arc.v] += arc.c;
rev.c += arc.c; arc.c = 0;
}
}
}
}
}
}
}
int main(){
//int T; cin >> T;
//for (int i=0;i
### External link :

[ZJU][2364][Data Transmission] Helanic Abyss

Andrew Stankevich』s Contest #3解題報告 by watashi