题目大意如题。
这道题想了很久也没明白题解的做法：
建边的时候每条边权 w = w * (E + 1) + 1;
这样得到最大流 maxflow / (E + 1) ，最少割边数 maxflow % (E + 1)
总之先把它当成黑科技背着吧
#include#include #include using namespace std;struct node { int from; int to; int w; int next;}e[160000];int cur[1500];int head[1500];int divv[1500];int cont, ss, tt;void add(int from, int to, int w) { e[cont].from = from; e[cont].w = w; e[cont].to = to; e[cont].next = head[from]; head[from] = cont++;}int n, m; int makedivv() { memset(divv, 0, sizeof(divv)); divv[ss] = 1; queue s; s.push(ss); while (!s.empty()) { int u = s.front(); if (u == tt)return 1; s.pop(); for (int i = head[u]; i != -1; i = e[i].next) { int w = e[i].w; int v = e[i].to; if (divv[v] == 0 && w) { divv[v] = divv[u] + 1; s.push(v); } } } return 0;}int Dfs(int u, int maxflow, int tt) { if (u == tt)return maxflow; int ret = 0; for (int &i = cur[u]; i != -1; i = e[i].next) { int v = e[i].to; int w = e[i].w; if (divv[v] == divv[u] + 1 && w) { int f = Dfs(v, min(maxflow - ret, w), tt); e[i].w -= f; e[i ^ 1].w += f; ret += f; if (ret == maxflow)return ret; } } return ret;}void Dinic() { long long int ans = 0; while (makedivv() == 1) { memcpy(cur, head, sizeof(head)); ans += Dfs(ss, 0x3f3f3f3f, tt); } printf("%lld\n", ans % 100000);}int main() { int t; scanf("%d", &t); while (t--) { scanf("%d%d", &n, &m); scanf("%d%d", &ss, &tt); cont = 0; memset(head, -1, sizeof(head)); for (int i = 0; i < m; i++) { int x, y, z; scanf("%d%d%d", &x, &y, &z); z = z * 100000 + 1; add(x, y, z); add(y, x, 0); } Dinic(); }}