[Poj3469]Dual Core CPU（最小割）

Description

题意：有n个任务，每个任务在机器A花费为ai,在机器B跑花费为bi,然后有m个关系（ai,bi,wi），表示如果ai,bi不在同一个机器上完成，额外的花费为wi，求最小的花费。

Solution

这是个最小割模型，把点分到2个集合里计算最小费用，就是求最小割

源点S向每个任务连ai的边，每个任务向汇点T连bi的边

对于每个关系只要2个任务间连一条双向边即可（割可能是正向或者逆向所以连双向边）

Code

#include <cstdio>
#include <algorithm>
#define N 20010
#define Inf 0x7fffffff
using namespace std;

struct info{int to,nex,f;}e[1000010];
int n,m,T,S,tot,nodes,head[N],Ans,cnt[N],dis[N];

inline void Link(int u,int v,int f){
    e[++tot].to=v;e[tot].nex=head[u];head[u]=tot;e[tot].f=f;
    e[++tot].to=u;e[tot].nex=head[v];head[v]=tot;e[tot].f=0;
}

inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

inline void Init(){
    n=read(),m=read();
    S=0,tot=1,nodes=(T=n+1)+1;
    for(int i=1;i<=n;++i){
    	int a=read(),b=read();
    	Link(S,i,a);
    	Link(i,T,b);
	}
	while(m--){
		int u=read(),v=read(),w=read();
		Link(u,v,w);
		Link(v,u,w);
	}
}

int sap(int u,int d){
    if(u==T) return d;
    int sum=0,mins=nodes;
    for(int i=head[u];i;i=e[i].nex){
        int v=e[i].to;
        if(e[i].f>0&&dis[u]==dis[v]+1){
            int save=sap(v,min(d-sum,e[i].f));
            sum+=save;
            e[i].f-=save;
            e[i^1].f+=save;
            if(dis[S]>=nodes||sum==d) return sum;
        }
        if(e[i].f>0) mins=min(mins,dis[v]);
    }
    if(!sum){
        if(!(--cnt[dis[u]])) dis[S]=nodes;
        else ++cnt[dis[u]=mins+1];
    }
    return sum;
}

void SAP(){cnt[0]=nodes;while(dis[S]<nodes) Ans+=sap(S,Inf);}

int main(){
    Init();
    SAP();
    printf("%d
",Ans);
    return 0;
}