Poj 3469 Dual Core CPU

http://poj.org/problem?id=3469

题意：有双核CPU，要运行N个模块，模块i在核A上花费是Ai，在B上为Bi。有M个相互交换数据的组合（ai，bi）。如果ai和bi在一块模块上，没有额外花费；如果不在，有额外花费wi。求最小　　　花费。

题解：这是一个典型的将最小费用的对象分为两个集合，转换为最小割的题。讲N个点分为两个集合，则花费有4部分组成，在A上执行的花费+在B上实行的花费+（ai在源点，bi在汇点）花费+

　　　（ai在汇点，bi在源点）花费->最小割->最大流

  1 #include <iostream>
  2 #include <cstring>
  3 #include <cstdio>
  4 #include <cstdlib>
  5 #include <cmath>
  6 #include <string>
  7 #include <vector>
  8 #include <list>
  9 #include <map>
 10 #include <queue>
 11 #include <stack>
 12 #include <bitset>
 13 #include <algorithm>
 14 #include <numeric>
 15 #include <functional>
 16 #include <set>
 17 #include <fstream>
 18 
 19 using namespace std;
 20 
 21 const int maxn=200010;
 22 const int INF=0x7fffffff;
 23 
 24 struct edge{
 25     int to,cap,rev;
 26 };
 27 vector<edge> G[maxn];
 28 int level[maxn];
 29 int iter[maxn];
 30 int A[maxn],B[maxn];
 31 int a[maxn],b[maxn],w[maxn];
 32 
 33 void add_edge(int from,int to,int cap)
 34 {
 35     G[from].push_back((edge){to,cap,(int)G[to].size()});
 36     G[to].push_back((edge){from,0,(int)G[from].size()-1});
 37 }
 38 
 39 void bfs(int s)
 40 {
 41     memset(level, -1, sizeof(level));
 42     queue<int> que;
 43     level[s]=0;
 44     que.push(s);
 45     while (!que.empty()) {
 46         int v=que.front();
 47         que.pop();
 48         for (int i=0; i<G[v].size(); i++) {
 49             edge &e=G[v][i];
 50             if (e.cap>0&&level[e.to]<0) {
 51                 level[e.to]=level[v]+1;
 52                 que.push(e.to);
 53             }
 54         }
 55     }
 56 }
 57 
 58 int dfs(int v,int t,int f)
 59 {
 60     if (v==t) {
 61         return f;
 62     }
 63     for (int &i=iter[v]; i<G[v].size(); i++) {
 64         edge &e=G[v][i];
 65         if (e.cap>0&&level[v]<level[e.to]) {
 66             int d=dfs(e.to, t, min(f,e.cap));
 67             if (d>0) {
 68                 e.cap-=d;
 69                 G[e.to][e.rev].cap+=d;
 70                 return d;
 71             }
 72         }
 73     }
 74     return 0;
 75 }
 76 
 77 int max_flow(int s,int t)
 78 {
 79     int flow=0;
 80     for (; ; ) {
 81         bfs(s);
 82         if (level[t]<0) {
 83             return flow;
 84         }
 85         memset(iter, 0, sizeof(iter));
 86         int f;
 87         while ((f=dfs(s, t, INF))>0) {
 88             flow+=f;
 89         }
 90     }
 91 }
 92 int main()
 93 {
 94     //freopen("/Users/apple/Desktop/POJ 3469/POJ 3469/in", "r", stdin);
 95     //freopen("/Users/apple/Desktop/POJ 3469/POJ 3469/out", "w", stdout);
 96     int N,M;
 97     while ((scanf("%d%d",&N,&M))!=EOF) {
 98         for (int i=0; i<N; i++) {
 99             scanf("%d%d",&A[i],&B[i]);
100         }
101         for (int i=0; i<M; i++) {
102             scanf("%d%d%d",&a[i],&b[i],&w[i]);
103         }
104         int s=N,t=s+1;
105         for (int i=0; i<N; i++) {
106             add_edge(i, t, A[i]);
107             add_edge(s, i, B[i]);
108         }
109         for (int i=0; i<M; i++) {
110             add_edge(a[i]-1, b[i]-1, w[i]);
111             add_edge(b[i]-1, a[i]-1, w[i]);
112         }
113         
114         printf("%d
",max_flow(s,t));
115     }
116     return 0;
117 }