构图思路:
1.将所有顶点v拆成两个点， v1,v2
2.源点S与v1连边，容量为 W-
3.v2与汇点连边，容量为 W+
4.对图中原边( a, b ), 连边 (a1,b2)，容量为正无穷大
则该图的最小割(最大流)即为最小花费。
简单证明： 根据ST割集的定义，将顶点分成两个点集。所以对于原图中的边(a,b),转换成 S->a1->b2->T. 则此时路径必定存在
一条割边，因为a1->b2为无穷大，所以割边必定是 S->a1 or b2->T, 若为前者则意味着删除a顶点的W-，后者则是b顶点的W+.
所以该图最小割即为最小花费。
计算方案： 对于构图后跑一次最大流，然后对于残留网络进行处理，首先从源点S出发，标记所有能访问到的顶点，这些顶点即为S割点集中
的顶点。 其他则为T集合中顶点， 然后从所有边中筛选出( A属于S,B属于T,且（A,B)容量为0 )的边，即为割边。因为我们的W+/W-边都只有一条，
且都分开了。比较容易处理。
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<string>
#include<vector>
#include<algorithm>
using namespace std; const int MAXN = ;
const int MAXM = ;
const int inf = 0x3f3f3f3f;
int A[MAXN], B[MAXN];
struct Edge{
int u, v, f, nxt;
}edge[];
int head[MAXN], idx;
int n, m;
int S, T, N; void AddEdge(int u,int v,int f){
edge[idx].u = u, edge[idx].v = v, edge[idx].f = f;
edge[idx].nxt = head[u]; head[u] = idx++;
edge[idx].u = v, edge[idx].v = u, edge[idx].f = ;
edge[idx].nxt = head[v]; head[v] = idx++;
} int h[MAXN], vh[MAXN];
int dfs(int u,int flow){
if(u == T) return flow;
int tmp = h[u]+, sum = flow;
for(int i = head[u]; ~i; i = edge[i].nxt){
if( edge[i].f && (h[edge[i].v]+ == h[u]) ){
int p = dfs( edge[i].v, min(sum,edge[i].f));
edge[i].f-=p, edge[i^].f+=p, sum-=p;
if( sum== || h[S]==N ) return flow-sum;
}
}
for(int i = head[u]; ~i; i = edge[i].nxt)
if( edge[i].f ) tmp = min( tmp, h[edge[i].v] );
if( --vh[ h[u] ] == ) h[S] = N;
else ++vh[ h[u]=tmp+ ];
return flow-sum;
}
int sap(){
int maxflow = ;
memset(h,,sizeof(h));
memset(vh,,sizeof(vh));
vh[] = N;
while( h[S] < N ) maxflow += dfs( S, inf );
return maxflow;
} bool vis[MAXN];
int res[MAXM]; void DFS(int u ){
vis[u] = true;
for(int i = head[u]; ~i; i = edge[i].nxt ){
int v = edge[i].v;
if( !vis[v] && edge[i].f )
DFS( v );
}
}
void solve(){
int maxflow = sap();
printf("%d\n", maxflow );
memset( vis,,sizeof(vis));
DFS( S ); int cnt = ;
for(int i = ; i < idx; i += ){
int u = edge[i].u, v = edge[i].v;
if( vis[u] && !vis[v] && (edge[i].f == ) )
res[cnt++] = i;
}
printf("%d\n", cnt );
for(int i = ; i < cnt; i++ ){
int u = edge[ res[i] ].u, v = edge[ res[i] ].v;
if( u == S ) printf("%d -\n", v);
else printf("%d +\n", u-n );
}
} int main(){
while( scanf("%d%d",&n,&m) != EOF ){
S = , T = *n+, N = *n+; idx = ;
memset( head, -, sizeof(head)); for(int i = ; i <= n; i++ )
scanf("%d", &A[i]);
for(int i = ; i <= n; i++ )
scanf("%d", &B[i]);
int a, b;
for(int i = ; i < m; i++ ){
scanf("%d%d", &a,&b);
AddEdge( a, n+b, inf );
}
for(int i = ; i <= n; i++){
AddEdge( S, i, B[i] ); // - out
AddEdge( n+i, T, A[i] );// + in
}
solve();
}
return ;
}