P1674 [USACO05FEB] Secret Milking Machine G 题解

· · 题解

这道题较水，就是一个二分+最大流

主要思路

看到求这种最大最小值的，第一直觉就是——二分。

简单证明一下，发现的确可以。

然后根据之前做题的经验，把边权小于等于 mid 的边的边权改为 1，大于的改为 0。

设源点为 1，汇点为 N，将无向图变为有向图（就是无向图中的每一条边都建正反两边），然后每次在二分时判断一下新建好的这个图中的最大流是否大于 T 即可。

但是，这里有一个问题：在题目中，要求一条路只能走一次，但在我们新建的有向图中，无向图中的边都已转化成两条边，所以相当于每一条路都有可能走两边。

其实我们不用担心，因为在网络流中，正向流一次，再反向流一次后，就相当于没流，抵消了。

进一步，我们发现，在代码上有一个空间上的小优化：在建残余网络时，我们还需要原网络中的每一条边再建一个正边和反边。也就是说题目中无向图的每一条边对应到我们的残余网络中，都有 4 条边。所以为了节省一下空间，我们可以将方向相同的两条边合并。

额。。。也许我说的不是很清楚，具体看代码吧。。。

AC Code

// 《 肥 肠 煎 蛋 》
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
#include <sstream>
#include <cstdio>
#include <queue>

using namespace std;

const int N = 205, M = 80005;

int h[N], e[M], ne[M], w[M], f[M], idx;
int n, m, S, T, t;
int d[N], cur[N];
bool vis[N];

void add(int a, int b, int c) {
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
    e[idx] = a, ne[idx] = h[b], w[idx] = c, h[b] = idx++;
}

bool bfs() {
    memset(vis, 0, sizeof(vis));
    memset(d, -1, sizeof(d)); 

    queue<int> q;

    q.push(S);
    d[S] = 0;
    vis[S] = 1;
    cur[S] = h[S];

    while (q.size()) {
        int t = q.front();

        q.pop();

        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];

            if (!vis[j] && f[i]) {
                vis[j] = 1;
                d[j] = d[t] + 1;
                cur[j] = h[j];

                if (j == T) return 1;

                q.push(j);
            }
        }
    }

    return 0;
}

int dfs(int u, int limit) {
    if (u == T) return limit;

    int flow = 0;
    for (int i = cur[u]; (~i) && flow < limit; i = ne[i]) {
        int j = e[i];

        cur[u] = i; 
        if (d[j] == d[u] + 1 && f[i]) {
            int k = dfs(j, min(f[i], limit - flow));

            if (!k) d[j] = -1;

            f[i] -= k;
            f[i ^ 1] += k;
            flow += k;
        }
    }

    return flow;
}

int dinic() {
    int r = 0, flow;

    while (bfs()) {
        while (flow = dfs(S, 1e9)) {
            r += flow;
        }
    }

    return r;
}

bool check(int x) {
    for (int i = 0; i < idx; i++) {
        if (w[i] <= x) f[i] = 1;
        else f[i] = 0;
    }

    return dinic() >= t;
}

int main() {
    memset(h, -1, sizeof(h));

    cin >> n >> m >> t;

    S = 1, T = n;
    for (int i = 1; i <= m; i++) {
        int a, b, c;

        cin >> a >> b >> c;

        add(a, b, c);
    }

    int l = 1, r = 1e6;

    while (l < r) {
        int mid = l + r >> 1;

        if (check(mid)) r = mid;
        else l = mid + 1;
    }

    cout << l << endl;

    return 0;
}

谢谢观看！