P1344 [USACO4.4] 追查坏牛奶 Pollutant Control （网络流）

题目链接

• P1344 [USACO4.4] 追查坏牛奶 Pollutant Control （网络流）
  • 题目描述
  • 输入格式
  • 输出格式
  • 样例 #1
    • 样例输入 #1
    • 样例输出 #1
  • 提示
  • 题目大意
  • 思路
  • 分析
  • code
• 双倍经验
  • 思路
  • code
• 后记

不会网络流的可以看这个

题目描述

你第一天接手三鹿牛奶公司就发生了一件倒霉的事情：公司不小心发送了一批有三聚氰胺的牛奶。

很不幸，你发现这件事的时候，有三聚氰胺的牛奶已经进入了送货网。这个送货网很大，而且关系复杂。你知道这批牛奶要发给哪个零售商，但是要把这批牛奶送到他手中有许多种途径。

送货网由一些仓库和运输卡车组成，每辆卡车都在各自固定的两个仓库之间单向运输牛奶。在追查这些有三聚氰胺的牛奶的时候，有必要保证它不被送到零售商手里，所以必须使某些运输卡车停止运输，但是停止每辆卡车都会有一定的经济损失。

你的任务是，在保证坏牛奶不送到零售商的前提下，制定出停止卡车运输的方案，使损失最小。

输入格式

第 \(1\) 行两个整数 \(N\)、\(M\)，\(N\) 表示仓库的数目，\(M\) 表示运输卡车的数量。仓库 \(1\) 代表发货工厂，仓库 \(N\) 代表有三聚氰胺的牛奶要发往的零售商。

第 \(2\sim M+1\) 行，每行 \(3\) 个整数 \(S_i\)、\(E_i\) 和 \(C_i\)。其中 \(S_i\)、\(E_i\) 分别表示这辆卡车的出发仓库和目的仓库。\(C_i\) 表示让这辆卡车停止运输的损失。

输出格式

两个整数 \(C\) 和 \(T\)，\(C\) 表示最小的损失，\(T\) 表示在损失最小的前提下，最少要停止的卡车数。

样例 #1

样例输入 #1

4 5
1 3 100
3 2 50
2 4 60
1 2 40
2 3 80

样例输出 #1

60 1

提示

对于 \(100 \%\) 的数据，满足 \(2 \le N \le 32\)，\(0 \le M \le 10^3\)，\(1 \le S_i \le N\)，\(1 \le E_i \le N\)，\(0 \le C_i \le 2 \times 10^6\)。

题目大意

现在有一个有向图，每一条边有一个边权表示删除这条边需要的代价，问你怎么操作，使得 \(1\to n\)

没有路径相连且代价最小，同时要求删除的最少路径。

思路

显然，这是求一个图的最小割问题，我们知道最大流等于最小割，所以求出最小割即可。

此时可能有很多种方案，我们需要求出这些方案中的最少路径数。

我们可以把所有边都乘上一个 \(a\) （建议取 \(1007\) ），再 \(+1\) 。

此时最大流记为 \(ans\)

那么 \(c = ans / a\) ，\(T = ans \mod a\)

分析

我们把所有边权 \(*a+1\) 后，答案又 \(/a\) 当路径小于 \(a\) 时是不影响 \(C\) 的。

然后 因为我们 \(+1\) 了，所以最小路径数仍然是最小割，其他路径就比最小割要大，摸上 \(a\) 后就是 \(T\) 了。

code

#include <bits/stdc++.h>
#define LL long long
#define fu(x, y, z) for (int x = y; x <= z; x++)
using namespace std;
const int N = 35, M = 1005, mod = 1007;
const LL Max = 1e15;
int n, m, d[N], vd[M], cnt = 1, hd[N];
LL ans, ans1, p[M << 1];
struct E {
    int to, nt, flg;
    LL w;
} e[M << 1];
void add(int x, int y, LL z) { e[++cnt].to = y, e[cnt].nt = hd[x], e[cnt].w = z, hd[x] = cnt; }
LL dfs(int x, LL pt) {
    LL now = pt, del = 0;
    int y, mind = n - 1;
    if (x == n) return pt;
    for (int i = hd[x]; i; i = e[i].nt) {
        if (!e[i].w) continue;
        y = e[i].to;
        if (d[x] == d[y] + 1) {
            del = min(e[i].w, now);
            del = dfs(y, del);
            now -= del;
            e[i].w -= del, e[i ^ 1].w += del;
            if (d[1] >= n)
                return pt - now;
            if (!now)
                break;
        }
        mind = min(mind, d[y]);
    }
    if (now == pt) {
        vd[d[x]]--;
        if (!vd[d[x]])
            d[1] = n;
        d[x] = mind + 1;
        vd[d[x]]++;
    }
    return pt - now;
}
LL flow() {
    LL sum = 0;
    fu(i, 1, n) d[i] = 0;
    vd[0] = n;
    while (d[1] < n) sum += dfs(1, Max);
    return sum;
}
int main() {
    int u, v;
    LL w;
    scanf("%d%d", &n, &m);
    fu(i, 1, m) {
        scanf("%d%d%lld", &u, &v, &w);
        p[cnt + 1] = w * mod + 1;
        add(u, v, w * mod + 1), add(v, u, 0);
    }
    ans = flow();
    printf("%lld %lld\n", ans / mod, ans % mod);
    // for (int i = 2; i <= cnt; i += 2) {
    //     fu(j, 2, cnt) if (!e[j].flg) e[j].w = p[j];
    //     e[i].w = 0;
    //     ans1 = flow();
    //     if (ans1 + p[i] == ans) {
    //         cout << i / 2 << "\n";
    //         e[i].flg = 1, e[i ^ 1].flg = 1, ans -= p[i];
    //     }
    // }
    return 0;
}

双倍经验

[OJ](追查坏牛奶 - 题目 - DYOJ)

思路

要求输出方案。

也就是看看那条是满流边。

我们把这条边暂时删掉之后看看现在的答案记为 \(ans1\) ，边权记为 \(e[i].w\) 是否满足

如果满足就是路径。

code

#include <bits/stdc++.h>
#define LL long long
#define fu(x , y , z) for(int x = y ; x <= z ; x ++)
using namespace std;
const int N = 35 , M = 1005 , mod = 1007;
const LL Max = 1e15;
int d[N] , vd[M] , n , m , hd[N] , cnt = 1;
LL ans , t , ans1 , p[M << 1];
struct E {
    int to , nt , flg;
    LL w;
} e[M << 1];
void add (int x , int y , int z) { e[++cnt].to = y , e[cnt].nt = hd[x] , e[cnt].w = z , hd[x] = cnt; }
LL dfs (int x , LL pt) {
    LL now = pt , del = 0;
    int mind = n - 1 , y;
    if (x == n) return pt;
    for (int i = hd[x] ; i ; i = e[i].nt) {
        if (!e[i].w) continue;
        y = e[i].to;
        if (d[x] == d[y] + 1) {
            del = min (now , e[i].w);
            del = dfs (y , del);
            now -= del;
            e[i].w -= del , e[i ^ 1].w += del;
            if (d[1] >= n) return pt - now;
            if (!now) break;
        }
        mind = min (mind , d[y]);
    }
    if (now == pt) {
        vd[d[x]] --;
        if (!vd[d[x]]) d[1] = n;
        d[x] = mind + 1;
        vd[d[x]] ++;
    }
    return pt - now;
}
LL flow () {
    LL sum = 0;
    vd[0] = n;
    fu (i , 1 , n) d[i] = 0;
    while (d[1] < n) {
        sum += dfs (1 , Max);
    }
    return sum;
}
int main () {
    int u , v;
    LL w;
    scanf ("%d%d" , &n , &m);
    fu (i , 1 , m) {
        scanf ("%d%d%lld" , &u , &v , &w);
        p[cnt + 1] = w * mod + 1;
        add (u , v , w * mod + 1) , add (v , u , 0);
    }
    ans = flow ();
    printf ("%lld %lld\n" , ans / mod , ans % mod);
    for (int i = 2 ; i <= cnt ; i += 2) {
        fu (j , 2 , cnt) if (!e[j].flg) e[j].w = p[j];
        e[i].w = 0;
        ans1 = flow ();
        if (ans1 + p[i] == ans) {
            cout << i / 2 << endl;
            e[i].flg = 1 , e[i ^ 1].flg = 1 , ans -= p[i];
        }
    }
    return 0;
}

后记

原题检测真的恶心！！！