Poj 3469 Dual Core CPU【最小割最大流-----Dinic】

Dual Core CPU

Time Limit: 15000MS		Memory Limit: 131072K
Total Submissions: 23103		Accepted: 10053
Case Time Limit: 5000MS

Description

As more and more computers are equipped with dual core CPU, SetagLilb, the Chief Technology Officer of TinySoft Corporation, decided to update their famous product - SWODNIW.

The routine consists of N modules, and each of them should run in a certain core. The costs for all the routines to execute on two cores has been estimated. Let's define them as A_i and B_i. Meanwhile, M pairs of modules need to do some data-exchange. If they are running on the same core, then the cost of this action can be ignored. Otherwise, some extra cost are needed. You should arrange wisely to minimize the total cost.

Input

There are two integers in the first line of input data, N and M (1 ≤ N ≤ 20000, 1 ≤ M ≤ 200000) .
The next N lines, each contains two integer, A_i and B_i.
In the following M lines, each contains three integers: a, b, w. The meaning is that if module a and module b don't execute on the same core, you should pay extra w dollars for the data-exchange between them.

Output

Output only one integer, the minimum total cost.

Sample Input

3 1

1 10

2 10

10 3

2 3 1000

Sample Output

13

Source

POJ Monthly--2007.11.25, Zhou Dong

 

题目大意:给你n个CPU，每个CPU都有两种mode，而且每个CPU只能选择一种mode运行，然后给你m个限制条件，a，b，c，如果a和b两个cpu用的不是一种mode，就需要c个花费来弥补这个问题,问每个CPU都运行的最小花费。

思路：

1、经典的最小割模型。建图如下：

①建立源点S，将其连入各个CPU，权值设定为Ai。

②建立汇点T，将各个CPU连入汇点，权值设定为Bi。

③对于m个限制，（a，b，c），将a连入b，权值设定为c，将b连入a，权值设定也是c。

2、那么为什么对于m个限制这样建图就能够达到目的选取最小割呢？

我们来看几个图：

①假设我们现在m==0

那么很明显，我们的最大流==最小割==2+3=5，同时也就是最小花费。跑得的残余网络：

那么我们加上一条限制，其权值设定为1000：

对应我们就能通过S-----2-------1-----------T继续增广。将对于2号CPU的选取mode从3变成了10，那么此时有限制的最小割==最大流==2+（3+7）=12；达到了目的、

3、所以按照上述建图方式是没有问题的，建好图之后直接跑最大流即可。

Ac代码：

#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
struct node
{
    int from;
    int to;
    int w;
    int next;
}e[3000005];
int head[120050];
int cur[120050];
int divv[120050];
int n,m,ss,tt,cont;
void add(int from,int to,int w)
{
    e[cont].to=to;
    e[cont].w=w;
    e[cont].next=head[from];
    head[from]=cont++;
}
int makedivv()
{
    queue<int >s;
    memset(divv,0,sizeof(divv));
    divv[ss]=1;
    s.push(ss);
    while(!s.empty())
    {
        int u=s.front();
        if(u==tt)return 1;
        s.pop();
        for(int i=head[u];i!=-1;i=e[i].next)
        {
            int v=e[i].to;
            int w=e[i].w;
            if(w&&divv[v]==0)
            {
                divv[v]=divv[u]+1;
                s.push(v);
            }
        }
    }
    return 0;
}
int Dfs(int u,int maxflow,int tt)
{
    if(u==tt)return maxflow;
    int ret=0;
    for(int &i=cur[u];i!=-1;i=e[i].next)
    {
        int v=e[i].to;
        int w=e[i].w;
        if(w&&divv[v]==divv[u]+1)
        {
            int f=Dfs(v,min(maxflow-ret,w),tt);
            e[i].w-=f;
            e[i^1].w+=f;
            ret+=f;
            if(ret==maxflow)return ret;
        }
    }
    return ret;
}
void Dinic()
{
    int ans=0;
    while(makedivv()==1)
    {
        memcpy(cur,head,sizeof(head));
        ans+=Dfs(ss,0x3f3f3f3f,tt);
    }
    printf("%d\n",ans);
}
int main()
{
    scanf("%d%d",&n,&m);
    cont=0;
    ss=n+1;
    tt=ss+1;
    memset(head,-1,sizeof(head));
    for(int i=1;i<=n;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        add(ss,i,a);
        add(i,ss,0);
        add(i,tt,b);
        add(tt,i,0);
    }
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);
        add(v,u,0);
        add(v,u,w);
        add(u,v,0);
    }
    Dinic();
}