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 Ai and Bi. 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.
POJ Monthly--2007.11.25, Zhou Dong
solution
先说做法再说想法。
设一个源，一个汇。
将源点与这n个点连n条有向边，容量为其A值；将这n个点与汇点连n条有向边，容量为其B值。
之后再在这n个点中连m条无向边。
再说注意点。每次写网络流都会发现一大堆坑爹点。
1.点数为20000 + 2个。。预定义宏的时候记得加括号。边数为点数 * 4 + M * 4 （无向）。
2.加边注意不要加反。。否则就2了。。。add(a,b,c){e[tot] = edge(b,v[a].next,c,tot + 1);//.....}
3.定义n的时候为最后一个点的下标，即输入的tn+1。于是cnt[0]要初始化为n + 1。距离最大值则为tn+1（n），即判定条件为d[i] < n + 1。
本题的解即为该网络的最小割。
详解：
随口说两句吧。别人建的模和图和咱建的也差不多。只不过我AC的时候完全没想明白是怎么个回事，随便建了个图就过了。不知道那些AC的人是不是有成熟的证明之后才过的。。。
只是觉得这个建图是显然的。
后来想想大概是这么一回事。
边分三种，入边（源到中继点），内边（中继点之间），出边（中继点到汇）。
对于流网络的任意割，每个中继点至少连接有一条割边中的入边或者出边，这对应着每个进程必须选择一个CPU，而如果割中出现了中边，那么就说明这两个中继点对应的进程分属不同的CPU，所以最小割对应着最小花费，yy结果显然。（具体证明请自行，本人蒟蒻，不会。）
#include <iostream>
#include <cstdio>
using namespace std;
#include <cstring>
#define maxn 20005
#define maxm (maxn * 4 + 200005 * 4)
const int inf = ~0u>>1;
struct edge
{
int p,next,val,anti;
edge(){}
edge(int a,int b,int c,int d):p(a),next(b),val(c),anti(d){}
}v[maxn],e[maxm],path[maxn],arc[maxn];
int flow[maxn],pre[maxn],d[maxn],cnt[maxn];
int tot,s,t,n;
void init()
{
tot = 0;
for(int i = 0;i <= n;i++)
{
v[i].next = -1;
d[i] = 0;
cnt[i] = 0;
}
cnt[0] = n + 1;
}
void add(int a,int b,int c)
{
e[tot] = edge(b,v[a].next,c,tot + 1);
v[a].next = tot++;
e[tot] = edge(a,v[b].next,0,tot - 1);
v[b].next = tot++;
}
int maxflow(int s,int t)
{
int total,i,k,loc,least,now;
bool flag;
for(int i = 0;i <= n;i++)
arc[i].next = v[i].next;
for(total = 0,i = s,now = inf;d[i] < n + 1;)
{
flow[i] = now;
for(flag = false,k = arc[i].next;~k;k = e[k].next)
{
if(e[k].val > 0 && d[i] == d[e[k].p] + 1)
{
now = min(e[k].val,now);
pre[e[k].p] = i;
path[e[k].p].next = k;
arc[i].next = k;
i = e[k].p;
if(i == t)
{
for(total += now;i != s;i = pre[i])
{
e[path[i].next].val -= now;
e[e[path[i].next].anti].val += now;
}
now = inf;
}
flag = true;
break;
}
}
if(!flag)
{
for(least = n,k = v[i].next;~k;k = e[k].next)
{
if(e[k].val && least > d[e[k].p])
{
loc = k;
least = d[e[k].p];
}
}
arc[i].next = loc;
cnt[d[i]]--;
if(cnt[d[i]] == 0)
break;
d[i] = least + 1;
cnt[d[i]] ++ ;
if(i != s)
{
i = pre[i];
now = flow[i];
}
}
}
return total;
}
int main()
{
int tn,tm;
scanf("%d %d",&tn,&tm);
n = tn + 1;
init();
for(int i = 1;i <= tn;i++)
{
int a,b;
scanf("%d %d",&a,&b);
add(0,i,a);
add(i,n,b);
}
for(int i = 0;i < tm;i++)
{
int a,b,c;
scanf("%d %d %d",&a,&b,&c);
add(a,b,c);
add(b,a,c);
}
printf("%d\n",maxflow(0,n));
}