题意：给出一张有可能自环、重边的有向图。每个节点i上都有两个值Wi+,Wi-，分别表示删掉所有i点的入边需要的代价和删掉所有i点的出边需要的代价。现在要求把所有的边全部删掉，求最小代价。
显然一条边只和个点有关，要删掉一条边(i,j)，要么付出Wi-，要么付出Wi+，很容易让人想到二分图。其实这就是一个二分图点权覆盖的问题。把每个点i拆为i,i'。对所有的Wi+，对应边(i',T,Wi+),对所有的Wi-.对应边(S,i,Wi-)，对于图中所有的边(u,v),对应边(u,v',inf)。然后求最小割就是答案。
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #define maxn 210 5 #define maxm 20000 6 #define INF 1<<30 7 using namespace std; 8 int v[maxm],next[maxm],w[maxm]; 9 int first[maxn],q[maxn],d[maxn],work[maxn]; 10 int e,S,T; 11 12 void init(){ 13 e = 0; 14 memset(first,-1,sizeof(first)); 15 } 16 17 void add_edge(int a,int b,int c){ 18 v[e] = b;next[e] = first[a];w[e] = c;first[a] = e++; 19 v[e] = a;next[e] = first[b];w[e] = 0;first[b] = e++; 20 } 21 22 int bfs(){ 23 int rear = 0; 24 memset(d,-1,sizeof(d)); 25 d[S] = 0;q[rear++] = S; 26 for(int i = 0;i < rear;i++){ 27 for(int j = first[q[i]];j != -1;j = next[j]) 28 if(w[j] && d[v[j]] == -1){ 29 d[v[j]] = d[q[i]] + 1; 30 q[rear++] = v[j]; 31 if(v[j] == T) return 1; 32 } 33 } 34 return 0; 35 } 36 37 int dfs(int cur,int a){ 38 if(cur == T) return a; 39 for(int &i = work[cur];i != -1;i = next[i]){ 40 if(w[i] && d[v[i]] == d[cur] + 1) 41 if(int t = dfs(v[i],min(a,w[i]))){ 42 w[i] -= t;w[i^1] += t; 43 return t; 44 } 45 } 46 return 0; 47 } 48 49 int dinic(){ 50 int ans = 0; 51 while(bfs()){ 52 memcpy(work,first,sizeof(first)); 53 if(int t = dfs(S,INF)) ans += t; 54 } 55 return ans; 56 } 57 58 int main() 59 { 60 int n,m; 61 while(scanf("%d%d",&n,&m) == 2){ 62 init(); 63 S = 0,T= 2*n+1; 64 for(int i = 1;i <= n;i++){ 65 int tmp; 66 scanf("%d",&tmp); 67 add_edge(n+i,T,tmp); 68 } 69 for(int i = 1;i <= n;i++){ 70 int tmp; 71 scanf("%d",&tmp); 72 add_edge(S,i,tmp); 73 } 74 for(int i = 0;i < m;i++){ 75 int a,b; 76 scanf("%d%d",&a,&b); 77 add_edge(a,b+n,INF); 78 } 79 int ans = dinic(); 80 printf("%d ",ans); 81 int cnt = 0; 82 int inq[maxn]; 83 for(int i = 1;i <= 2*n;i++){ 84 if(d[i] != -1 && i > n) inq[cnt++] = i; 85 if(d[i] == -1 && i <= n)inq[cnt++] = i; 86 } 87 printf("%d ",cnt); 88 for(int i = 0;i < cnt;i++){ 89 if(inq[i] > n) printf("%d + ",inq[i]-n); 90 else printf("%d - ",inq[i]); 91 } 92 } 93 return 0; 94 }