ISAP算法求最大流，根據最大流最小割定理，實際這道題求的是最小割，以前我們的網絡流都是常用流量表示解答方案，而這道題是以割的性質出發，流隻是求最小割的手段
如果有感興趣的同學可以看 2001 - 江鵬：《從一道題目的解法試談網絡流的構造與算法》，這裡有一點值得注意的是，因為每個子產品都被兩個CPU利用，是以我們建立雙相弧在CPU與子產品之間。。
#include<iostream>
#include<cstdio>
#include<string.h>
#include<string>
#include<stack>
#include<set>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
#include<sstream>
#include<queue>
#define ll __int64
#define lll unsigned long long
#define MAX 1000009
#define MAXN 2009
#define eps 1e-8
#define INF 0x7fffffff
#define mod 1000000007
#define clr(a) memset(a,0,sizeof(a))
#define clr1(a) memset(a,-1,sizeof(a))
#define lson l , m , rt << 1
#define rson m + 1 , r , rt << 1 | 1
using namespace std;
inline ll Max(ll a,ll b)
{
return a>b?a:b;
}
inline ll Min(ll a,ll b)
{
return a<b?a:b;
}
const int N = 20009;
struct Edge
{
int from,to,flow,cap;
};
struct ISAP
{
int n,m,s,t;
vector<Edge>edges;
vector<int>G[N];
int p[N];//可增廣的上一條弧
int num[N];//距離标号計數
bool vis[N];
int d[N];
int cur[N];
void addedge(int from,int to,int cap)
{
edges.push_back((Edge)
{
from,to,0,cap
});
edges.push_back((Edge)
{
to,from,0,cap//雙相弧
});
m = edges.size();
G[from].push_back(m - 2);
G[to].push_back(m - 1);
}
bool BFS()
{
clr(vis);
queue<int>Q;
Q.push(t);
d[t] = 0;
vis[t] = 1;
while(!Q.empty())
{
int x = Q.front();
Q.pop();
for(int i = 0; i<G[x].size(); i++)
{
Edge& e = edges[G[x][i]^1];
if(!vis[e.from]&&e.cap>e.flow)
{
vis[e.from] = 1;
d[e.from] = d[x] + 1;
Q.push(e.from);
}
}
}
return vis[s];
}
int Augment()
{
int x = t;
int a = INF;
while(x!=s)
{
Edge& e = edges[p[x]];
a = min(a,e.cap - e.flow);
x = edges[p[x]].from;
}
x = t;
while(x!=s)
{
edges[p[x]].flow+=a;
edges[p[x]^1].flow-=a;
x = edges[p[x]].from;
}
return a;
}
ll MaxFlow(int s,int t)
{
this->s = s;
this->t = t;
ll flow = 0;
BFS();
clr(num);
for(int i = 0; i<=n; i++) num[d[i]]++;
int x = s;
clr(cur);
while(d[s]<n)
{
if(x==t)
{
//cout<<Augment()<<endl;
flow+= Augment();
x = s;
}
int ok = 0;
for(int i = cur[x]; i<G[x].size(); i++)
{
Edge& e = edges[G[x][i]];
if(e.cap>e.flow&&d[x]==d[e.to] + 1)//Advance
{
ok = 1;
p[e.to] = G[x][i];
cur[x] = i;
x = e.to;
break;
}
}
if(!ok)//Retreat
{
int m = n -1;
for(int i = 0; i<G[x].size(); i++)
{
Edge& e = edges[G[x][i]];
if(e.cap>e.flow) m = min(m,d[e.to]);
}
if(--num[d[x]]==0)break;
num[d[x] = m + 1]++;
cur[x] = 0;
if(x!=s) x = edges[p[x]].from;
}
}
return flow;
}
};
int main()
{
#ifdef ONLINE_JUDGE
#else
freopen("an.txt","r", stdin);
#endif
int m,n;
int u,v,w1,w2;
while(~scanf("%d%d",&n,&m))
{
ISAP x;
x.n = n + 1;
for(int i = 1; i<=n; i++)
{
scanf("%d%d",&w1,&w2);
x.addedge(0,i,w1);
x.addedge(i, n + 1, w2);
}
for(int i = 0; i<m; i++)
{
scanf("%d%d%d",&u,&v,&w1);
x.addedge(u,v,w1);
}
printf("%d\n",x.MaxFlow(0,n +1));
}
return 0;
}