如何用网络流算法解决ACMICPC Qingdao Online比赛中的最小割与最短路问题？

本文共计999个文字，预计阅读时间需要4分钟。

帝国再次遭受攻击。帝国将军正计划保卫他的城堡。这片土地由N个城镇和M条道路组成，每条道路长度相同，连接两个城镇。编号为1的城镇是将军的城堡所在地。

The empire is under attack again. The general of empire is planning to defend his castle. The land can be seen as N towns and M roads, and each road has the same length and connects two towns. The town numbered 1 is where general’s castle is located, and the town numbered N is where the enemies are staying. The general supposes that the enemies would choose a shortest path. He knows his army is not ready to fight and he needs more time. Consequently he decides to put some barricades on some roads to slow down his enemies. Now, he asks you to find a way to set these barricades to make sure the enemies would meet at least one of them. Moreover, the barricade on the i-th road requires wi units of wood. Because of lacking resources, you need to use as less wood as possible.
Input
The first line of input contains an integer t, then t test cases follow.
For each test case, in the first line there are two integers N(N≤1000) and M(M≤10000).
The i-the line of the next M lines describes the i-th edge with three integers u,v and w where 0≤w≤1000 denoting an edge between u and v of barricade cost w.
Output
For each test cases, output the minimum wood cost.
Sample Input
1
4 4
1 2 1
2 4 2
3 1 3
4 3 4
Sample Output
4
题意很简单；
做法：在最短路上面跑一下最大流最小割

#include<iostream> #include<cstdio> #include<algorithm> #include<cstdlib> #include<cstring> #include<string> #include<cmath> #include<map> #include<set> #include<vector> #include<queue> #include<string> #include<bitset> #include<ctime> #include<deque> typedef long long ll; using namespace std; typedef unsigned long long int ull; #define maxn 200005 #define ms(x) memset(x,0,sizeof(x)) #define Inf 0x7fffffff #define inf 0x3f3f3f3f const long long int mod = 1e9 + 7; #define pi acos(-1.0) #define pii pair<int,int> #define eps 1e-7 #define pll pair<ll,ll> ll quickpow(ll a, ll b) { ll ans = 1; a = a % mod; while (b > 0) { if (b % 2)ans = ans * a; b = b / 2; a = a * a; } return ans; } int gcd(int a, int b) { return b == 0 ? a : gcd(b, a%b); } struct node { int v, len, w; node(){} node(int v,int len,int w):v(v),len(len),w(w){} }; struct edge { int to, cap, rev; edge(){} edge(int to,int cap,int rev):to(to),cap(cap),rev(rev){} }; int n; vector<node>g[maxn]; vector<edge>G[maxn]; int d[maxn]; bool vis[maxn]; void addedge(int u, int v, int cap) { G[u].push_back(edge(v, cap, G[v].size())); G[v].push_back(edge(u, 0, G[u].size() - 1)); } int dfs(int v, int t, int f) {// 增广路 if (v == t)return f; vis[v] = true; for (int i = 0; i < G[v].size(); i++) { edge &e = G[v][i]; if (!vis[e.to] && e.cap > 0) { int d = dfs(e.to, t, min(f, e.cap)); if (d > 0) { e.cap -= d; G[e.to][e.rev].cap += d; return d; } } } return 0; } int maxflow(int s, int t) { int flow = 0; while (1) { ms(vis); int f = dfs(s, t, inf); if (f == 0) { return flow; } flow += f; } } void sol() { for (int i = 1; i <= n; i++) { int len = g[i].size(); for (int j = 0; j < len; j++) { int v = g[i][j].v; int l = g[i][j].len; int w = g[i][j].w; if (d[v] - d[i] == l) { addedge(i, v, w); } } } } void spfa(int x) { int v[maxn]; ms(v); queue<int>q; q.push(x); v[x] = 1; d[x] = 0; while (!q.empty()) { int nod = q.front(); q.pop(); v[nod] = 0; for (int i = 0; i < g[nod].size(); i++) { int nxtnod = g[nod][i].v; if (d[nxtnod] > d[nod] + g[nod][i].len) { d[nxtnod] = d[nod] + g[nod][i].len; if (!v[nxtnod]) { v[nxtnod] = 1; q.push(nxtnod); } } } } } void init() { memset(d, 1, sizeof(d)); for (int i = 0; i < maxn - 1; i++) { g[i].clear(); G[i].clear(); } } int main() { ios::sync_with_stdio(false); int t; cin >> t; while (t--) { int m; cin >> n >> m; init(); for (int i = 0; i < m; i++) { int u, v, w; cin >> u >> v >> w; g[u].push_back(node(v, 1, w)); g[v].push_back(node(u, 1, w)); } spfa(1); sol(); ll ans = maxflow(1, n); cout << ans << endl; } }