题意：给出一张n个点m条边的有向图。现在编号为1的城市想进攻编号为n的城市。n为了防御1的进攻，需要破坏一些道路使得1到n不连通，而破坏每条路都有一个代价，题目会告诉你。现在编号为1的城市想要让编号为n的城市花费尽量多的代价来破坏道路使得1到n不连通，因此他们可以在2-n中的任意城市间修一条无坚不摧的桥（这条桥既可以是原来存在的也可以是原来不存在的），问n花费的最大代价。
本来想先求一遍最小割，然后还原网络，把所有的割边的容量设为inf，求一遍最大流这样得到结果的。但是存在1到n不连通的情况，因此就不能求出最小割了。所以用到了一个更加暴力的方法。先求一遍最大流，得到maxflow，这是如果没有修桥的情况下的最小花费。然后枚举所有S所在的源集中的非S点a和T所在的汇集中的非T点b，假设他们之间的边被修成了不可摧毁的桥，这时候需要额外付出多少代价呢。答案就在残量网络里，就是从S到a的最小割与b到T的最小割中较小的那个。那就之间在a到b之间加一条cap=inf的边，然后从S到T跑最大流就可以了，得到答案ans。最后的答案就是maxflow+ans。
代码：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #define INF 1<<30 6 #define maxn 110 7 #define maxm 20000 8 using namespace std; 9 10 int v[maxm],next[maxm],w[maxm]; 11 int first[maxn],d[maxn],work[maxn],q[maxn]; 12 int _v[maxm],_next[maxm],_w[maxm]; 13 int src_set[maxn],sink_set[maxn]; 14 int e,S,T,n,m; 15 16 void init(){ 17 e = 0; 18 memset(first,-1,sizeof(first)); 19 } 20 21 void add_edge(int a,int b,int c){ 22 v[e] = b;next[e] = first[a];w[e] = c;first[a] = e++; 23 v[e] = a;next[e] = first[b];w[e] = 0;first[b] = e++; 24 } 25 26 int bfs(){ 27 int rear = 0; 28 memset(d,-1,sizeof(d)); 29 d[S] = 0;q[rear++] = S; 30 for(int i = 0;i < rear;i++){ 31 for(int j = first[q[i]];j != -1;j = next[j]) 32 if(w[j] && d[v[j]] == -1){ 33 d[v[j]] = d[q[i]] + 1; 34 q[rear++] = v[j]; 35 if(v[j] == T) return 1; 36 } 37 } 38 return 0; 39 } 40 41 int dfs(int cur,int a){ 42 if(cur == T) return a; 43 for(int &i = work[cur];i != -1;i = next[i]){ 44 if(w[i] && d[v[i]] == d[cur] + 1) 45 if(int t = dfs(v[i],min(a,w[i]))){ 46 w[i] -= t;w[i^1] += t; 47 return t; 48 } 49 } 50 return 0; 51 } 52 53 int dinic(){ 54 int ans = 0; 55 while(bfs()){ 56 memcpy(work,first,sizeof(first)); 57 while(int t = dfs(S,INF)) ans += t; 58 } 59 return ans; 60 } 61 62 int main() 63 { 64 int kase; 65 scanf("%d",&kase); 66 while(kase--){ 67 init(); 68 scanf("%d%d",&n,&m); 69 S = 1,T = n; 70 for(int i = 0;i < m;i++){ 71 int a,b,c; 72 scanf("%d%d%d",&a,&b,&c); 73 add_edge(a,b,c); 74 } 75 int maxflow = dinic(); 76 for(int i = 0;i < e;i++){ 77 _v[i] = v[i],_next[i] = next[i],_w[i] = w[i]; 78 } 79 int src_cnt = 0,sink_cnt = 0; 80 for(int i = 2;i < n;i++){ 81 if(d[i] != -1) src_set[src_cnt++] = i; 82 else sink_set[sink_cnt++] = i; 83 } 84 int ans = 0; 85 for(int i = 0;i < src_cnt;i++){ 86 for(int j = 0;j < sink_cnt;j++){ 87 for(int k = 0;k < e;k++) 88 v[k] = _v[k],next[k] = _next[k],w[k] = _w[k]; 89 add_edge(src_set[i],sink_set[j],INF); 90 int tmp = dinic(); 91 if(tmp > ans) ans = tmp; 92 first[src_set[i]] = next[e-2]; 93 first[sink_set[j]] = next[e-1]; 94 e -= 2; 95 } 96 } 97 printf("%d ",maxflow+ans); 98 } 99 return 0; 100 }