学步园

链接：http://poj.org/problem?id=3469

题意：有一个双核CPU，有n个模块需要在cpu上处理，在两个核上运行的耗费分别是Ai和Bi，m对模块需要共享数据，如果它们运行在同一个cpu中，共享数据的耗费可以忽略不计，否则需要额外的费用。求最小总耗费值。

思路：将两个cpu视为源点、汇点，模块视为图中顶点，对于每个Ai和Bi，可以从源点连一条容量为Ai的弧到i，从i连一条容量为Bi的弧到汇点，对于两个模块之间需要共享数据的情况，在它们之间连两条弧，正向和反向，容量为额外耗费，此时每个顶点都和源点、汇点相连，即每个顶点都可以在任意一个cpu中运行。

这样构图，对于图中任意一个割，源点、汇点都不是连通的，因此每个顶点都不可能同时和源点及汇点相连，也即每个顶点只能在一个cpu中运行。此时耗费即为割的容量，要让割的容量最小，根据最大流最小割定理，只需求原图的最大流即可。

isap

#include<cstring>
#include<string>
#include<fstream>
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cctype>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
#include<vector>
#include<stack>
#include<ctime>
#include<cstdlib>
#include<functional>
#include<cmath>
using namespace std;
#define PI acos(-1.0)
#define MAXN 500100
#define eps 1e-7
#define INF 0x7FFFFFFF
#define LLINF 0x7FFFFFFFFFFFFFFF
#define seed 131
#define mod 1000000007
#define ll long long
#define ull unsigned ll
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1

struct node{
    int u,v,w,next;
}edge[1000000];
int head[20010],dist[20010],cur[20010],fa[20010],num[20010],vis[20010];
int n,m,k,cnt,nn,src,sink;
void add_edge(int a,int b,int c){
    edge[cnt].u = a;
    edge[cnt].v = b;
    edge[cnt].w = c;
    edge[cnt].next = head[a];
    head[a] = cnt++;
}
void bfs()
{
    int x,i,j;
    queue<int> q;
    memset(dist,-1,sizeof(dist));
    memset(num,0,sizeof(num));
    q.push(sink);
    dist[sink] = 0;
    num[0] = 1;
    while(!q.empty()){
        x = q.front();
        q.pop();
        for(i=head[x];i!=-1;i=edge[i].next){
            if(dist[edge[i].v]<0){
                dist[edge[i].v] = dist[x] + 1;
                num[dist[edge[i].v]]++;
                q.push(edge[i].v);
            }
        }
    }
}

int augment()
{
    int x=sink,a=INF;
    while(x!=src){
        a = min(a,edge[fa[x]].w);
        x = edge[fa[x]].u;
    }
    x=sink;
    while(x!=src){
        edge[fa[x]].w -= a;
        edge[fa[x]^1].w += a;
        x = edge[fa[x]].u;
    }
    return a;
}

int isap()
{
    int i,x,ok,minm,flow=0;
    bfs();
    for(i=0;i<=nn+5;i++) cur[i] = head[i];
    x=src;
    while(dist[src]<nn){
        if(x==sink){
            flow += augment();
            x = src;
        }
        ok=0;
        for(i=cur[x];i!=-1;i=edge[i].next){
            if(edge[i].w && dist[x]==dist[edge[i].v]+1){
                ok=1;
                fa[edge[i].v] = i;
                cur[x] = i;
                x = edge[i].v;
                break;
            }
        }
        if(!ok){
            minm = nn;
            for(i=head[x];i!=-1;i=edge[i].next)
                if(edge[i].w && dist[edge[i].v]<minm)   minm=dist[edge[i].v];
            if(--num[dist[x]]==0)break;
            num[dist[x]=minm+1]++;
            cur[x]=head[x];
            if(x!=src)  x=edge[fa[x]].u;
        }
    }
    return flow;
}
int main(){
    int i,j;
    int a,b,c;
    memset(head,-1,sizeof(head));
    scanf("%d%d",&n,&m);
    cnt = 0;
    src = 0;
    sink = n + 1;
    nn = sink + 2;
    for(i=1;i<=n;i++){
        scanf("%d%d",&a,&b);
        add_edge(src,i,a);
        add_edge(i,src,0);
        add_edge(i,sink,b);
        add_edge(sink,i,0);
    }
    for(i=0;i<m;i++){
        scanf("%d%d%d",&a,&b,&c);
        add_edge(a,b,c);
        add_edge(b,a,0);
        add_edge(b,a,c);
        add_edge(a,b,0);
    }
    int ans = isap();
    printf("%d\n",ans);
    return 0;
}