POJ3469Dual Core CPU

题意：给你n个模块，每个模块在A核花费为ai,在B核跑花费为bi,然后由m个任务（ai,bi,wi），表示如果ai,bi不在同一个核上跑，额外的花费为wi，求最小的花费。

分析： 用最小的费用将对象划分成两个集合的问题，常常可以转化成最小割后解决，这题就是一道经典的问题；

1.考虑把N个模块按照在那个核执行分成两个集合。在A执行为集合S，B为T。

2.当模块属于A集的时候，花费为ai，所以就从向t连一条ai的边，而当模块属于B集的时候，花费为bi，所以就由s连一条向bi的边。然后对于每个任务，当ai,bi不同的时候花费为mi，所以就由ai,bi连两条容量为wi的边，跑一下最大流就可以得出对应的最小花费了

3.为什么会想到这些呢？首先来了解下：最小割，就是在流向图上去掉数量最少容量最小的边，使这个图变得不连通，源点s无法到达汇点t，这些边组成的容量就是最小割。那我们是不是可以想到，与最小费用进行对比，如果我们建的图是满足最小割为答案的话，那我们就可以很容易解决问题了；

4. 大佬文献

代码：

#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<cmath>
#include<queue>
#define ll long long
#define maxn 23500
#define maxe 1000000
#define inf 1100000000
using namespace std;
 
struct Edge
{
    int u, v, cap;
    int nxt;
}edge[maxe];
 
int head[maxn];
int n, m;
 
struct Dicnic
{
    int level[maxn];
    int iter[maxn];
    int add;
    void init(){
        add = 0; memset(head, -1, sizeof(head));
        memset(iter, -1, sizeof(iter));
    }
    void insert(int u, int v, int c){
        edge[add].u = u; edge[add].v = v; edge[add].cap = c;
        edge[add].nxt = head[u]; head[u] = add++;
        edge[add].u = v; edge[add].v = u; edge[add].cap = 0;
        edge[add].nxt = head[v]; head[v] = add++;
    }
    void bfs(int s){
        memset(level, -1, sizeof(level));
        queue<int> que;
        level[s] = 0;
        que.push(s);
        while (!que.empty()){
            int v = que.front(); que.pop();
            for (int i = head[v]; i != -1; i = edge[i].nxt){
                Edge &e = edge[i];
                if (e.cap > 0 && level[e.v] < 0){
                    level[e.v] = level[v] + 1;
                    que.push(e.v);
                }
            }
        }
    }
 
    int dfs(int v, int t, int f){
        if (v == t) return f;
        for (int &i = iter[v]; i != -1; i = edge[i].nxt){
            Edge &e = edge[i]; Edge &reve = edge[i ^ 1];
            if (e.cap > 0 && level[v] < level[e.v]){
                int d = dfs(e.v, t, min(f, e.cap));
                if (d>0){
                    e.cap -= d; reve.cap += d;
                    return d;
                }
            }
        }
        return 0;
    }
 
    int max_flow(int s, int t){
        int flow = 0;
        for (;;){
            bfs(s);
            if (level[t] < 0) return flow;
            memcpy(iter, head, sizeof(iter));
            int f;
            while ((f = dfs(s, t, inf))>0){
                flow += f;
            }
        }
    }
}net;
 
int a[maxn], b[maxn];
 
int main()
{
    while (cin >> n >> m){
        net.init();
        int s = 0, t = n + 1;
        for (int i = 1; i <= n; i++) {
            scanf("%d", a + i); scanf("%d", b + i);
            net.insert(i, t, a[i]);
            net.insert(s, i, b[i]);
        }
        int ui, vi, wi;
        for (int i = 0; i < m; i++){
            scanf("%d%d%d", &ui, &vi, &wi);
            net.insert(ui, vi, wi);
            net.insert(vi, ui, wi);
        }
        printf("%d
", net.max_flow(s,t));
    }
    return 0;
}