P1344 [USACO4.4] 追查坏牛奶 Pollutant Control
大意
在保证坏牛奶不送到零售商的前提下，制定出停止卡车运输的方案，使损失最小。
思路
这个题目要求的是要求费用最小下的最小割的数量，我们采用一种权值偏移法，首先确定一个 \(BASE\)，然后就是在网络流赋容量的时候，就服为 \(c \times BASE + 1\)，这样算出的答案 \(ans / BASE\) 就是最小损失，\(ans \mod BASE\) 就是最小的割的数量。
代码
#include<bits/stdc++.h>
using namespace std;#define int long long
const int MAXN = 1005;
const int MAXM = 1005;
int n, m, S, T;struct node{int v, nxt, c;
}e[MAXM << 2];
int h[MAXN], d[MAXN], cur[MAXN];
int tot;void add(int u, int v, int c){e[tot] = {v, h[u], c};h[u] = tot ++;
}void init(){tot = 0;memset(h, -1, sizeof(h));
}bool bfs(){queue<int> q;memset(d, -1, sizeof(d));d[S] = 0;q.push(S);while(!q.empty()){int u = q.front();q.pop();for(int i = h[u];~i;i = e[i].nxt){int v = e[i].v;if(e[i].c && d[v] == -1){d[v] = d[u] + 1;q.push(v);}}}return (d[T] == -1) ? false : true;
}int dfs(int u, int flow){if(u == T){return flow;}int res = 0;for(int &i = cur[u];~i;i = e[i].nxt){int v = e[i].v;if(e[i].c && d[v] == d[u] + 1){int tmp = dfs(v, min(flow, e[i].c));e[i].c -= tmp;flow -= tmp;e[i ^ 1].c += tmp;res += tmp;if(!flow) break;}}if(!res){d[u] = -1;}return res;
}int Dinic(){int res = 0;while(bfs()){memcpy(cur, h, sizeof(h));res += dfs(S, 1e9);}return res;
}vector<int> vec;
bool vis[MAXN];
void dfs1(int u){vec.push_back(u);vis[u] = 1;for(int i = h[u];~i;i = e[i].nxt){int v = e[i].v;if(e[i].c && !vis[v]){dfs1(v);}}
}signed main(){
// freopen("road.in", "r", stdin);
// freopen("road.out", "w", stdout);init();cin >> n >> m;S = 1, T = n;const int BASE = MAXM;for(int i = 1;i <= m;i ++){int u, v, w, op; cin >> u >> v >> w;w = w * BASE + 1;add(u, v, w); add(v, u, 0);}int max_flow = Dinic();cout << max_flow / BASE << ' ' << max_flow % BASE << '\n';return 0;
}