Control HDU - 4289
题意： 在一张双向交通网络图中，在交查路口都要安排一个警察来监视，每个路口警察都有不同的花费，要求监视到所有的车辆人员，求最小花费。
思路： 其实这里利用网络流的流量是其路径上的最小容量限制的（即我们说的割），用网络流来找到最小花费，我们拆点为边，把点拆为入点和出点，把放置警察的花费作为边的容量，道路是双向的，从一个点的出点到另一个点的入点，容量设置为无穷inf建图跑网络流就可以了。
code：
#include<iostream> #include<cstdio> #include<cstdlib> #include<cmath> #include<algorithm> #include<queue> using namespace std; const int maxn = 4e2 + 5; const int inf = 2e9 + 5; const int inf_se = 1e7 + 5; struct edges{ int u, v, w, next; } g[maxn * maxn]; int head[maxn], gap[maxn], dep[maxn], cnt; void init(int n){ cnt = 0; for(int i = 0; i <= n; i++){ head[i] = -1; } } void add(int u, int v, int w){ g[cnt].u = u; g[cnt].v = v; g[cnt].w = w; g[cnt].next = head[u]; head[u] = cnt++; } void bfs(int n, int t){ for(int i = 1; i <= n; i++){ dep[i] = -1; } queue<int> qu; while(qu.size()) qu.pop(); qu.push(t); dep[t] = 0; while(qu.size()){ int u = qu.size(); qu.pop(); for(int i = head[u]; i != -1; i = g[i].next){ int v = g[i].v; if(g[i ^ 1].w > 0 && dep[v] == -1) dep[v] = dep[u] + 1, qu.push(v); } } for(int i = 0; i <= n; i++) gap[i] = 0; for(int i = 1; i <= n; i++) gap[dep[i]]++; } int dfs(int n, int s, int t, int u, int limit){ if(u == t || limit == 0) { return limit; } int flow = 0, f; bool flag = true; for(int i = head[u]; i != -1; i = g[i].next){ int v = g[i].v; if( g[i].w > 0 && dep[u] == dep[v] + 1 && (f = dfs(n, s, t, v, min(g[i].w, limit))) ){ g[i].w -= f; g[i ^ 1].w += f; limit -= f; flow += f; flag = false; } } if(flag){ int min_dep = n - 1; for(int i = head[u]; i != -1; i = g[i].next) if(g[i].w > 0) min_dep = min(min_dep, dep[g[i].v]); if(--gap[dep[u]] <= 0) dep[s] = n; dep[u] = min_dep + 1; gap[dep[u]]++; } return flow; } int isap(int n, int s, int t){ int flow = 0; bfs(n, t); while(dep[s] < n){ flow += dfs(n, s, t, s, inf); } return flow; } int main(){ int n, m, s, t; int sum[maxn]; while(~scanf("%d%d%d%d", &n, &m, &s, &t)) { init(n * 2); for(int i = 1; i <= n; i++) scanf("%d", &sum[i]); for(int i = 1; i <= n; i++){ add(i * 2 - 1, i * 2, sum[i]); add(i * 2, i * 2 - 1, 0); } int u, v; for(int i = 1; i <= m; i++){ scanf("%d%d", &u, &v); add(u * 2, v * 2 - 1, inf_se); add(v * 2 - 1, u * 2, 0); add(v * 2, u * 2 - 1, inf_se); add(u * 2 - 1, v * 2, 0); } // for(int i = 0; i < cnt; i++){ // printf("u = %d v = %d w = %d\n", g[i].u, g[i].v, g[i].w); // } printf("%d\n", isap(n * 2, s * 2 - 1, t * 2)); } }