题意：一个国家的地图是一张n个点m条边的有向图。你保卫了国家成为了英雄，现在国王答应给你一些城市。国王居住在首都，编号为1，但他不想随意的到达你的领地，所以你必须破坏一些路，使得从首都到你所拥有的所有城市不连通。而破坏这些路需要花钱。国王给了你f个城市供你选择，每个城市有一个价值。你最后的总收益=你选择的城市的价值之和-破坏路花费的钱。现在让你输出最大的收益，以及完成这样的收益应该破坏哪些路。
首先对于表示这个国家地图的有向边(u,v,cost)，直接在图中建一条一样的边(u,v,cost)。对于供你选择的城市i，假设它的价值是value，创建一个汇点T，建一条(i,T,value)的边。然后以1为源点，T为汇点，求最小割即可。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #define INF 1<<30 6 #define maxn 1010 7 #define maxm 300000 8 using namespace std; 9 10 int u[maxm],v[maxm],next[maxm],w[maxm]; 11 int first[maxn],d[maxn],work[maxn],q[maxn],vis[maxn]; 12 int e,S,T,n,m,f; 13 bool f1[maxn],f2[maxn]; 14 15 void init(){ 16 e = 0; 17 memset(first,-1,sizeof(first)); 18 } 19 20 void add_edge(int a,int b,int c){ 21 u[e] = a;v[e] = b;next[e] = first[a];w[e] = c;first[a] = e++; 22 u[e] = b;v[e] = a;next[e] = first[b];w[e] = 0;first[b] = e++; 23 } 24 25 int bfs(){ 26 int rear = 0; 27 memset(d,-1,sizeof(d)); 28 d[S] = 0;q[rear++] = S; 29 for(int i = 0;i < rear;i++){ 30 for(int j = first[q[i]];j != -1;j = next[j]) 31 if(w[j] && d[v[j]] == -1){ 32 d[v[j]] = d[q[i]] + 1; 33 q[rear++] = v[j]; 34 if(v[j] == T) return 1; 35 } 36 } 37 return 0; 38 } 39 40 int dfs(int cur,int a){ 41 if(cur == T) return a; 42 for(int &i = work[cur];i != -1;i = next[i]){ 43 if(w[i] && d[v[i]] == d[cur] + 1) 44 if(int t = dfs(v[i],min(a,w[i]))){ 45 w[i] -= t;w[i^1] += t; 46 return t; 47 } 48 } 49 return 0; 50 } 51 52 int dinic(){ 53 int ans = 0; 54 while(bfs()){ 55 memcpy(work,first,sizeof(first)); 56 while(int t = dfs(S,INF)) ans += t; 57 } 58 return ans; 59 } 60 61 void dfs1(int u){ 62 f1[u] = 1; 63 for(int i = first[u];i != -1;i = next[i]){ 64 if(!f1[v[i]] && w[i]) dfs1(v[i]); 65 } 66 } 67 68 void dfs2(int u){ 69 f2[u] = 1; 70 for(int i = first[u];i != -1;i = next[i]){ 71 if(!f2[v[i]] && w[i^1]) dfs2(v[i]); 72 } 73 } 74 75 int p[100010],res[100010]; 76 77 void min_cnt(){ 78 memset(f1,0,sizeof(f1)); 79 memset(f2,0,sizeof(f2)); 80 dfs1(S); 81 dfs2(T); 82 /*for(int i = 1;i <= n;i++) 83 printf("f1[%d] = %d ",i,f1[i]); 84 for(int i = 1;i <= n;i++) 85 printf("f2[%d] = %d ",i,f2[i]);*/ 86 int cnt = 0; 87 for(int i = 1;i <= m;i++){ 88 if(f1[u[p[i]]] && f2[v[p[i]]] && !w[p[i]]){ 89 res[cnt++] = i; 90 } 91 } 92 printf("%d",cnt); 93 for(int i = 0;i < cnt;i++) printf(" %d",res[i]); 94 printf(" "); 95 } 96 97 int main() 98 { 99 int nkase; 100 scanf("%d",&nkase); 101 for(int kase = 1;kase <= nkase;kase++){ 102 init(); 103 int sum = 0; 104 scanf("%d%d%d",&n,&m,&f); 105 S = 1,T = n+1; 106 for(int i = 1;i <= m;i++){ 107 int a,b,c; 108 scanf("%d%d%d",&a,&b,&c); 109 p[i] = e; 110 add_edge(a,b,c); 111 } 112 for(int i = 1;i <= f;i++){ 113 int a,b; 114 scanf("%d%d",&a,&b); 115 sum += b; 116 add_edge(a,T,b); 117 } 118 printf("Case %d: %d ",kase,sum-dinic()); 119 min_cnt(); 120 } 121 return 0; 122 }