题目描述：
由于越来越多的计算机配置了双核CPU，TinySoft 公司的首席技术官员，SetagLilb，决定升级他们的产品－SWODNIW。SWODNIW 包含了N 个模块，每个模块必须运行在某个CPU 中。每个模块在每个CPU 中运行的耗费已经被估算出来了，设为Ai 和Bi。同时，M 对模块之间需要共享数据，如果他们运行在同一个CPU 中，共享数据的耗费可以忽略不计，否则，还需要额外的费用。你必须很好地安排这N 个模块，使得总耗费最小。
输入描述：
测试数据的第1 行为两个整数N 和M，1≤N≤20000，1≤M≤200000。接下来有N 行，每行为两个整数Ai 和Bi。接下来有M 行，每行为3 个整数a, b, w，表示a 模块和b 模块如果不是在同一个CPU 中运行，则需要花费额外的w 耗费来共享数据。
输出描述：输出一个整数，为最小耗费。
样例输入：
3 1
1 10
2 10
10 3
2 3 1000
样例输出：
13
这题有点神了，Dinic算法TLE了好多发啊！！！Dinic这T得无语了！后面实在不行看别人博客了！原来Dinic还有多路增广这做法，太神了！！！
就是在dfs的时候多路增广……好神……做为网络流更快的模板了……再学习下sap优化就差不多了……
这题还有点其实就是构图刚开始的时候我是有向图的，然后做着做着得有反向边啊，然后想了想，原来就是无向图而已……有向边加上其反向边就是一个强连通了，那么相当于没有方向一样了……
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <list>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <set>
#define PI acos(-1.0)
#define mem(a,b) memset(a,b,sizeof(a))
#define sca(a) scanf("%d",&a)
#define pri(a) printf("%d\n",a)
#define MM 1000002
#define MN 22005
#define INF 168430090
using namespace std;
typedef long long ll;
int n,m,cnt,d[MN],head[MM],go[MM],q[MM];
struct node
{
int v,w,next;
}e[MM];
void add(int u,int v,int w)
{
e[cnt].v=v; e[cnt].w=w; go[cnt]=cnt+1; //go数组的作用是记住反向边的邻接表下标，下同
e[cnt].next=head[u]; head[u]=cnt++;
e[cnt].v=u; e[cnt].w=0; go[cnt]=cnt-1; //反向边权值为0
e[cnt].next=head[v]; head[v]=cnt++;
}
int bfs()
{
mem(d,-1);
int left=0,right=0;
q[right++]=0; d[0]=0;
while(left<right) //找增广路
{
int u=q[left++];
for(int v=head[u];v!=-1;v=e[v].next)
{
if(d[e[v].v]==-1&&e[v].w)
{
d[e[v].v]=d[u]+1; //分层，越往后，层数越大
if(e[v].v!=n+1) q[right++]=e[v].v;
}
}
}
return d[n+1]!=-1;
}
int dfs(int u,int Min)
{
int sum,duolu=0;
if(u==n+1) return Min;
for(int v=head[u];v!=-1&&Min-duolu>0;v=e[v].next) //Min-duolu这个多路增广的做法真神！
if(e[v].w&&d[e[v].v]==d[u]+1&&(sum=dfs(e[v].v,min(Min-duolu,e[v].w))))
{
e[v].w-=sum;
e[go[v]].w+=sum;
duolu+=sum;
}
return duolu;
}
void Dinic()
{
int tmp,ans=0;
while(bfs())
{
while(tmp=dfs(0,INF))
ans+=tmp;
}
printf("%d\n",ans);
}
int main()
{
scanf("%d%d",&n,&m);
int u,v,w,i,a,b;
mem(head,-1);
for(i=1;i<=n;i++)
{
scanf("%d%d",&a,&b);
add(0,i,a); add(i,n+1,b);
}
while(m--)
{
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);
}
Dinic();
return 0;
}