题意：给定一个分层图，即只能够在相邻层次之间流动，给定了各个顶点的层次。要求输出一个阻塞流。
分析：该题直接Dinic求最大流TLE了，网上说采用Isap也TLE，而最大流中的最高标号预流推进（HLPP）能够直接秒掉这一题。当然还有一种挽救的方式就是首先进行一次贪心预流，然后进行dinic。也是第一次听说还有贪心预流这回事，所以找了一份代码特地学习了一番。具体步骤如下：
1.首先将所有节点按照层次进行排序，对每个节点有in[i]和out[i]两个属性，前者表示能够流入到该节点的流量，后者表示能够流出该节点的流量；
2.从层次最低的节点（即源点）开始，设in[S] = inf，表示源点能够进入无限的流量，然后按照层次的递增来推流量，维护好每个节点的in和out值；
3.从层次最高的节点（即汇点）开始，将所有节点的in都清空为0，设in[T] = inf，表示汇点能够收集无限的流量，然后从后往前计算出每条边实际能够流动的流量。
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <queue>
using namespace std; const int N = ;
const int M = ;
const int inf = 0x3f3f3f3f;
int n, m, L, SS, TT;
int lv[N], rank[N], in[N], out[N]; struct Edge {
int v, c, nxt;
}e[M<<];
int idx, head[N];
int dis[N];
char vis[N];
queue<int>q; void insert(int a, int b, int c) {
e[idx].v = b, e[idx].c = c;
e[idx].nxt = head[a];
head[a] = idx++;
} bool bfs() {
memset(dis, 0xff, sizeof (dis));
memset(vis, , sizeof (vis));
dis[SS] = , vis[SS] = ;
q.push(SS);
while (!q.empty()) {
int u = q.front();
q.pop();
vis[u] = ;
for (int i = head[u]; ~i; i = e[i].nxt) {
int v = e[i].v, c = e[i].c;
if (dis[v] == - && c) {
dis[v] = dis[u] + ;
if (!vis[v]) {
vis[v] = ;
q.push(v);
}
}
}
}
return dis[TT] != -;
} int dfs(int u, int flow) {
if (u == TT) return flow;
int tf = , f;
for (int i = head[u]; ~i; i = e[i].nxt) {
int v = e[i].v, c = e[i].c;
if (dis[u]+ == dis[v] && c && (f = dfs(v, min(flow-tf, c)))) {
e[i].c -= f, e[i^].c += f;
tf += f;
if (tf == flow) return tf;
}
}
if (!tf) dis[u] = -;
return tf;
} void dinic() {
while (bfs()) {
dfs(SS, inf);
}
} bool cmp(const int &a, const int &b) {
return lv[a] < lv[b];
} void greedy() {
memset(in, , sizeof (in));
memset(out, , sizeof (out));
sort(rank+, rank++n, cmp);
in[SS] = inf;
for (int i = ; i <= n; ++i) {
int u = rank[i];
for (int j = head[u]; ~j; j = e[j].nxt) {
int v = e[j].v, c = e[j].c;
if (!(j & ) && in[u] > out[u]) {
int f = min(c, in[u]-out[u]);
in[v] += f, out[u] += f;
}
}
}
memset(in, , sizeof (in));
in[TT] = inf;
for (int i = n; i >= ; --i) {
int v = rank[i];
for (int j = head[v]; ~j; j = e[j].nxt) {
int u = e[j].v, c = e[j^].c;
if (j & && out[u] > in[u]) {
int f = min(c, min(out[u]-in[u], in[v]));
in[u] += f, in[v] -= f;
e[j].c += f, e[j^].c -= f;
}
}
}
} int main() {
int T;
scanf("%d", &T);
while (T--) {
idx = ;
memset(head, 0xff, sizeof (head));
scanf("%d %d %d", &n, &m, &L);
for (int i = ; i <= n; ++i) {
rank[i] = i;
scanf("%d", &lv[i]);
if (lv[i] == ) SS = i;
else if (lv[i] == L) TT = i;
}
int a, b, c;
for (int i = ; i < m; ++i) {
scanf("%d %d %d", &a, &b, &c);
insert(a, b, c), insert(b, a, );
}
greedy(), dinic();
for (int i = ; i < m; ++i) {
printf("%d\n", e[i<<|].c);
}
}
return ;
}