题目链接： http://poj.org/problem?id=3469
题意： 给出A，B两个内核，给出N个进程，每个进程在不同的内核花费不一样，再给出M个任务，每个任务是a，b两个进程在交换数据，如果在同一内核就不需要额外花费，如果在不同内核则需要额外花费。求N个进程都跑起来并且满足M个任务的条件下的最小花费。
分析： 先不考虑M个任务，我们发现每个进程要么属于A，要么属于B，我们可以类比网络流里的S集合和T集合，那么我们从源点向每个进程建边，容量为Ai；从每个进程向汇点建边，容量为Bi，那么最小割恰好也就是每个进程划分好的最小花费：从源点跑到汇点，每个进程的流量都是最小的那个，所以最终就是最小花费。然后再这个基础上，M个任务的建边就是在a,b两个进程间再建一条容量为c的边，相当于强行扩大了原来网络流的流量：如果之前所有满边都在同一个集合的话，这些新加的边不会对最大流量（即等同最大花费）产生影响，但如果这条边所连的两个进程在不同的集合中的话，这条相当于又给没跑满的边增加了出路：即增加了流量（增加了花费）。在这样建边的情况下，最后划分出来的两个集合得到的最小割就一定是最小花费了。
图示： 如果没有交换数据的任务进程，我们发现最小花费的边限制了流量，即最终跑出的最大流就是整体的最小花费：200+300=500 如果我们在b，c进程间添加一个数据交换的任务，花费为800，即建了一条容量为800的双向边。这样之前S->b没有跑满的边，又可以通过b->c跑出新的流量，直到跑满b->T，c->T，相当于b,c在同一个集合了，且得到最大流量也就是最小花费：200+300+200=700。
AC代码：
/************************************************************************* > File Name: test.cpp > Author: Akira > Mail: qaq.febr2.qaq@gmail.com ************************************************************************/ #include <iostream> #include <sstream> #include <cstdio> #include <cstring> #include <string> #include <cstdlib> #include <algorithm> #include <bitset> #include <queue> #include <stack> #include <map> #include <cmath> #include <vector> #include <set> #include <list> #include <ctime> #include <climits> typedef long long LL; typedef unsigned long long ULL; typedef long double LD; #define MST(a,b) memset(a,b,sizeof(a)) #define CLR(a) MST(a,0) #define Sqr(a) ((a)*(a)) using namespace std; #define MaxN 200010 #define MaxM MaxN*44 #define INF 0x3f3f3f3f #define PI 3.1415926535897932384626 const int mod = 1E9+7; const double eps = 1e-6; #define bug cout<<88888888<<endl; #define debug(x) cout << #x" = " << x; struct Edge{ int u,v,next; int flow; }edge[MaxM]; //最大边数，一般都是实际边数的2倍甚至以上 int head[MaxN]; int cont; void init(){ //记得init cont = 0; MST(head, -1); } void add(int u, int v, int flow){ edge[cont].u = u; edge[cont].v = v; edge[cont].flow = flow; edge[cont].next = head[u]; head[u] = cont++; } void Add(int u, int v, int flow){ //建正反两条边，反向流量为0 add(u, v, flow); add(v, u, 0); } int dis[MaxN]; int num[MaxN]; int cur[MaxN]; int pre[MaxN]; void BFS(int source,int sink) { queue<int>q; CLR(num); MST(dis,-1); q.push(sink); dis[sink]=0; num[0]=1; while(!q.empty()) { int u=q.front(); q.pop(); for(int i=head[u];i!=-1;i=edge[i].next) { int v = edge[i].v; if(dis[v] == -1) { dis[v] = dis[u] + 1; num[dis[v]]++; q.push(v); } } } } int ISAP(int source,int sink,int n) //从源点到汇点，n为总点数，返回最大流 { memcpy(cur,head,sizeof(cur)); int flow=0, u = pre[source] = source; BFS( source,sink); while( dis[source] < n ) { if(u == sink) { int df = INF, pos; for(int i =source;i != sink;i = edge[cur[i]].v) { if(df > edge[cur[i]].flow) { df = edge[cur[i]].flow; pos = i; } } for(int i = source;i != sink;i = edge[cur[i]].v) { edge[cur[i]].flow -= df; edge[cur[i]^1].flow += df; } flow += df; //cout << flow << endl; u = pos; } int st; for(st = cur[u];st != -1;st = edge[st].next) { if(dis[edge[st].v] + 1 == dis[u] && edge[st].flow) { break; } } if(st != -1) { cur[u] = st; pre[edge[st].v] = u; u = edge[st].v; } else { if( (--num[dis[u]])==0 ) break; int mind = n; for(int id = head[u];id != -1;id = edge[id].next) { if(mind > dis[edge[id].v] && edge[id].flow != 0) { cur[u] = id; mind = dis[edge[id].v]; } } dis[u] = mind+1; num[dis[u]]++; if(u!=source) u = pre[u]; } } return flow; } int N,M; int main() { //std::ios::sync_with_stdio(false); while(~scanf("%d%d", &N, &M)) { init(); int s = 0, t=N+1; for(int i=1;i<=N;i++) { int x,y; scanf("%d%d", &x, &y); Add(s,i,x); Add(i,t,y); } while(M--) { int a,b,c; scanf("%d%d%d", &a, &b, &c); Add(a,b,c); Add(b,a,c); } cout << ISAP(s,t,N+1) << endl; } //system("pause"); }