题目大意：n个工作，2个CPU，每个工作都可以工作在2个CPU上，并且对于工作i，在第一个CPU上工作的代价为ai，在第二个CPU上工作的代价是bi，再给m对工作，每对工作有数据交换，如果这2个工作工作在同一个CPU上，数据交换无代价，否则数据交换代价为w。求n个工作完成的最小代价。
题目分析：有2个CPU，每个工作只能工作在一个CPU上，所以我们可以将所有的工作分成2类：工作在第一个CPU上和工作在第二个CPU上的。于是就将所有的点分成了2个集合，每个集合中有若干个工作，并且2个CPU只能在2个集合中。很显然有割的性质，此题求一个最小割，根据最大流最小割定理，求最大流即可。
关于建图：要求最小代价。以2个CPU为源点和汇点。假设A为源点，B为汇点。对于工作i，源点与i建一条边，边权为bi，i与汇点建一条边，边权为ai。因为要求最小割，所以我们要想象割的过程，如果让工作i工作在A CPU上，那么就要割断工作i和B CPU的联系，那么割断这个联系的代价便是工作i工作在A CPU上的代价，所以i到汇点建边的边权要为ai。对于m个工作关系，同样想象割的过程：如果工作i，j工作在同一块CPU上，那么代价为0，如果工作在不同的CPU上，那么这2个工作必须分开，于是工作i和j直接就要有一个割，割的代价就是w，所以对于每对有联系的工作，之间相互建边，边权为w。
这题数据量比较大，测试模版比较不错。
详情请见代码：
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 20005;
const int M = 200005;
const int NM = 1000005;
const int inf = 0x3f3f3f3f;
int n,m,num;
int head[N];
int que[N],sta[N],cnt[N],dis[N],rpath[N];
struct node
{
int to,c,next,pre,f;//
}arc[NM];
void build(int s,int e,int cap)
{
arc[num].to = e;
arc[num].c = cap;
arc[num].f = 0;
arc[num].next = head[s];
head[s] = num ++;
arc[num - 1].pre = num;
arc[num].pre = num - 1;
arc[num].to = s;
arc[num].f = 0;
arc[num].c = 0;
arc[num].next = head[e];
head[e] = num ++;
}
void re_Bfs()
{
int i,front,rear;
for(i = 0;i <= n + 1;i ++)
{
dis[i] = inf;
cnt[i] = 0;
}
rear = front = 0;
que[rear ++] = n + 1;
dis[n + 1] = 0;
cnt[0] = 1;
while(front != rear)
{
int u = que[front ++];
for(i = head[u];i != -1;i = arc[i].next)
{
if(arc[arc[i].pre].c == 0 || dis[arc[i].to] < inf)
continue;
dis[arc[i].to] = dis[u] + 1;
cnt[dis[arc[i].to]] ++;
que[rear ++] = arc[i].to;
}
}
}
void ISAP()
{
re_Bfs();
int i,u,v,maxflow = 0;
for(i = 0;i <= n + 1;i ++)
sta[i] = head[i];
u = 0;
while(dis[0] < n + 2)
{
if(u == n + 1)
{
int curflow = inf;
for(i = 0;i != n + 1;i = arc[sta[i]].to)
curflow = min(curflow,arc[sta[i]].c);
for(i = 0;i != n + 1;i = arc[sta[i]].to)
{
arc[sta[i]].c -= curflow;
arc[arc[sta[i]].pre].c += curflow;
arc[sta[i]].f += curflow;
arc[arc[sta[i]].pre].f -= curflow;
}
maxflow += curflow;
u = 0;
}
for(i = sta[u];i != -1;i = arc[i].next)
if(arc[i].c > 0 && dis[u] == dis[arc[i].to] + 1)
break;
if(i != -1)
{
sta[u] = i;
rpath[arc[i].to] = arc[i].pre;
u = arc[i].to;
}
else
{
if((-- cnt[dis[u]]) == 0)
break;
sta[u] = head[u];
int Min = inf;
for(i = head[u];i != -1;i = arc[i].next)
if(arc[i].c > 0)
Min = min(Min,dis[arc[i].to]);
dis[u] = Min + 1;
cnt[dis[u]] ++;
if(u != 0)
u = arc[rpath[u]].to;
}
}
printf("%d\n",maxflow);
}
int main()
{
int i,a,b,w;
//freopen("data.in","r",stdin);
while(scanf("%d",&n) != EOF)
{
scanf("%d",&m);
memset(head,-1,sizeof(head));
num = 0;
for(i = 1;i <= n;i ++)
{
scanf("%d%d",&a,&b);
build(i,n + 1,a);
build(0,i,b);
}
for(i = 1;i <= m;i ++)
{
scanf("%d%d%d",&a,&b,&w);
build(a,b,w);
build(b,a,w);//important;
}
ISAP();
}
return 0;
}
//14944K 2782MS