题目描述：

在一个有向图中，对于每个点，有两个值，删除这个点入度的边，代价为w+，删除出度的边，代价为w-
用最小的代价移走所有的边，问你最小的代价和具体的删除方式。

题目描述：

二分图最小点权覆盖

对于n个点，拆点。分别为1~n和n+1~2n

一个超级源点s，和1~n连接，容量为w-

一个超级汇点t，和n+1~2n连接，容量为w+

对于边ab，连接a到b+n，容量无穷大。

这样求得的最大流值就是最小权值。

证明：
割的性质是不存在一条从s到t的路径。
故对于每一条边a和b的路径：s-a-b-t中至少有一条边在割集中。
而ab又是无限大，所以它不会在割集中，则sa或者bt至少一个在最小割中，正好和题意相符合。

然后是找一个符合最优解得最小割集。

 

任意最小割。首先对网络求一次最大流，再对求完最大流的残余网络求一次FloodFill，访问到的点属于S集合，没有访问到的点属于T集合。则从S集合到T集合的边即为最小割集。

 

代码如下：

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define size 500
#define Max 0x7fffffff
int cap[size][size],s,t,n;
int queue[size],head,tail, Flow,prev[size];
bool findload()      //bfs找增广路径
{
 int i, tmp;
 memset(prev,-1,sizeof(prev));
 head = tail = 0;;
 queue[tail++] = s;
 prev[s] = s;
 while(head < tail)
 {
  tmp = queue[head++];
  for(i = 0; i <= t; i++)
   if(prev[i] == -1 && cap[tmp][i] > 0)
   {
    prev[i] = tmp;
    if (i == t) return true;
    queue[tail++] = i;
   }
 }
 return false;
}
int maxflow()
{
    Flow = 0;
 while(findload())
 {
  int min = Max;
  for(int i = t; i != s; i = prev[i])  //增广路径中的最小可通过流
   if(min > cap[prev[i]][i])
    min = cap[prev[i]][i];
  for(int i = t; i != s; i = prev[i])//调整路径上的流
  {
   cap[prev[i]][i] -= min;
   cap[i][prev[i]] += min;
  }
  Flow += min;   //最大流累加
 }
 return Flow;
}
int m, w, a, b, re[size];
int main()
{
    scanf("%d%d", &n, &m); memset(cap, 0, sizeof(cap));
    s = 0, t = (n * 2) + 1;
    for(int i = 1; i <= n; i++){scanf("%d", &w);cap[i + n][t] = w;}
    for(int i = 1; i <= n; i++){scanf("%d", &w);cap[s][i] = w;}
    for(int i = 0; i < m; i++) {scanf("%d%d", &a, &b);cap[a][b + n] = Max;}
    int ans = maxflow(), cnt = 0;
    for(int i = 1; i <= t; i++)
    {
        if (prev[i] == -1 && i <= n) cnt++;
        if (prev[i] != -1 && i > n) cnt++;
    }printf("%d\n%d\n", ans, cnt);
    for(int i = 1; i <= t; i++)
    {
        if (prev[i] != -1 && i > n) printf("%d +\n", i - n);
        if (prev[i] == -1 && i <= n) printf("%d -\n", i);
    }
    return 0;
}