USACO4.4 Pollutant Control

网络流

Luogu

题目很明显是要求最小割，但是竟然要最小化边数？

我开始是想着将每一条边的费用设为 $1$ 来跑费用流。。然后发现有反例

我们可以将每一条边的费用乘上一个大数再加上 $1$，然后再跑最大流

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
typedef long long LL;
#define int LL
const int INF = 0x3f3f3f3f;
const int MAXN = 32;
const int MAXM = 1000;
const int MOD = 10000;
int n, m, edge = -1, maxFlow;
int firstEdge[MAXN | 1], curEdge[MAXN | 1], depth[MAXN | 1];
struct Edge {
    int to, f, nxt;
    Edge(){}
    Edge(int x, int y, int z) {
        to = y;
        f = z;
        nxt = firstEdge[x];
    }
} e[MAXM << 1 | 1];
inline int read() {
    register int x = 0;
    register char ch = getchar();
    while(!isdigit(ch)) ch = getchar();
    while(isdigit(ch)) {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x;
}
inline void addEdge(int x, int y, int z) {
    e[++edge] = Edge(x, y, z);
    firstEdge[x] = edge;
}
bool getDepth() {
    std::queue <int> q;
    memset(depth, 0, sizeof(depth));
    depth[1] = 1;
    q.push(1);
    do {
        int from = q.front();
        q.pop();
        for(int k = firstEdge[from]; ~k; k = e[k].nxt) {
            int to = e[k].to, f = e[k].f;
            if(f > 0 && !depth[to]) {
                depth[to] = depth[from] + 1;
                q.push(to);
            }
        }
    } while(!q.empty());
    return depth[n] > 0;
}
int Augment(int x, int flow) {
    if(x == n) return flow;
    for(int &k = curEdge[x]; ~k; k = e[k].nxt) {
        int to = e[k].to, f = e[k].f;
        if(f > 0 && depth[to] == depth[x] + 1) {
            int tmp = Augment(to, std::min(flow, f));
            if(tmp > 0) {
                e[k].f -= tmp;
                e[k ^ 1].f += tmp;
                return tmp;
            }
        }
    }
    return 0;
}
int Dinic() {
    int tmp = 0;
    while(getDepth()) {
        for(int i = 1; i <= n; ++i) curEdge[i] = firstEdge[i];
        while((tmp = Augment(1, INF)) > 0) maxFlow += tmp;
    }
} 
signed main() {
    n = read();
    m = read();
    memset(firstEdge, -1, sizeof(firstEdge));
    for(int i = 1; i <= m; ++i) {
        int a = read(), b = read(), c = read();
        addEdge(a, b, c * MOD + 1);
        addEdge(b, a, 0);
    }
    Dinic();
    printf("%lld %lld\n", maxFlow / MOD, maxFlow % MOD);
    return 0;
}