题意：
给出N个点和M条边
再给出ai和bi。
ai表示删除i的所有入边的权值
bi表示删除i的所有出边的权值
然后给出那些边。
求怎样用最小的代价，删除所有的边。
分析：
详细的可以看amber的最小割论文
http://u.115.com/file/f7142414ae
过期的话就百度一下吧。。。
具体名字是《最小割模型在信息学竞赛中的应用》
就是最小点权覆盖（用最少的点权覆盖所有的边）
我们把每个点拆成两个点。
对于每个bi，建边(S,i,bi)
对于每个ai，建边(i+n,T,ai)
然后每条图中的边，建边(i,j+n,INF)
然后求最大流，最后求最小割即可。
插曲：
一开始ai和bi弄反了。WA到SB了
code：
#include
#define E 2000000
#define INF 0x7FFFFFFF
using namespace std;
struct edge{int x,y,c,op,next;}g[E];
int n,e=0,ls[N],fa[N],cur[N],d[N],num[N],v[N],ans[N];
void add(int x,int y,int c){
e++;
g[e].x=x; g[e].y=y; g[e].c=c; g[e].op=e+1; g[e].next=ls[x]; ls[x]=e;
e++;
g[e].x=y; g[e].y=x; g[e].c=0; g[e].op=e-1; g[e].next=ls[y]; ls[y]=e;
}
void init(){
memset(ls,0,sizeof(ls));
memset(fa,0,sizeof(fa));
memset(cur,0,sizeof(cur));
memset(d,0,sizeof(d));
memset(num,0,sizeof(num));
memset(v,0,sizeof(v));
int m,x,y;
cin >> n >> m;
for (int i=1;i<=n;i++){
cin >> x;
add(i+n,n+n+1,x);
}
for (int i=1;i<=n;i++){
cin >> x;
add(0,i,x);
}
for (int i=1;i<=m;i++){
cin >> x >> y;
add(x,y+n,INF);
}
}
void relabel(int k){
cur[k]=ls[k];
int min=n+n+1;
for (int i=ls[k];i!=0;i=g[i].next)
if (g[i].c>0 && d[g[i].y]
}
int change(){
int nf=INF;
for (int i=n+n+1;i!=0;i=g[fa[i]].x)
nf=min(nf,g[fa[i]].c);
for (int i=n+n+1;i!=0;i=g[fa[i]].x){
g[fa[i]].c-=nf;
g[g[fa[i]].op].c+=nf;
}
return nf;
}
int sap(){
int flow=0;
for (int i=0;i<=n+n+1;i++) cur[i]=ls[i];
num[0]=n+n+2;
int i=0;
while (d[0]
if (g[cur[i]].c>0 && d[g[cur[i]].y]+1==d[i]) break;
if (cur[i]==0){
if (–num[d[i]]==0) break;
relabel(i);
num[d[i]]++;
if (i!=0) i=g[fa[i]].x;
}
else{
fa[g[cur[i]].y]=cur[i];
i=g[cur[i]].y;
if (i==n+n+1){
flow+=change();
i=0;
}
}
}
return flow;
}
void dfs(int k){
d[k]=1;
v[k]=0;
for (int i=ls[k];i!=0;i=g[i].next)
if (d[g[i].y]==0 && g[i].c>0) dfs(g[i].y);
}
void print(){
int t=0;
for (int i=0;i<=N;i++) v[i]=1;
memset(d,0,sizeof(d));
dfs(0);
for (int i=1;i<=e;i=i+2)
if (v[g[i].x]==0 && v[g[i].y]==1 && g[i].c==0)
ans[t++]=i;
cout << t << endl;
for (int i=0;i
else cout << g[ans[i]].x-n<<" +" << endl;
}
int main(){
init();
int flow=sap();
cout << flow << endl;
print();
}
