题意： 有一个有 N 个节点M 条边的的有向图，每个点对应两种操作：

          将该点所有入边删除 ‘+’ ，对应一个花费，将该点所有出边删除 ‘ - ’亦对应一个花费

          问如何操作将所有边删除使得花费的总和最小。

分析：  建图:

           将每个点拆分成两个点， i（左点） 和 i+n（右点） ,

           建立一个源点 s=0,汇点 u=2*n+1

           在源点和每个点左面的点连一条边，容量为删除出边的费用

           在汇点和每个点右面的点连一条边，容量为删除入边的费用

           如果有 u 到 v 的边，在u 和 v +n 之间连一条边，容量为无穷大

           求出最大流即最小割

           从源点深搜找出残流不为 0 的点，把这些点标记掉，剩下的为标记的点即为删除的顶点。

 

#include
     
      #include
      
       #include
       
        #define INF 0x1f1f1f1f#define min(a,b)(a)<(b)?(a):(b)#define clr(x)memset(x,0,sizeof(x))#define maxn 210struct node{    int c,next,to;}e[100000];int tot;int head[maxn];void add(int s,int t,int flow){    e[tot].to=t;    e[tot].c=flow;    e[tot].next=head[s];    head[s]=tot++;}int max_flow(int st,int end,int n){    int numh[maxn],h[maxn],edge[maxn],pre[maxn];    int cur_flow,maxflow=0,u,tmp,neck,i;    clr(h);  clr(numh);    memset(pre,0xff,sizeof(pre));    for(i=0;i<=n;i++)        edge[i]=head[i];    numh[0]=n+1;    u=st;    while(h[st]
        
         e[edge[i]].c)                {                    neck=i;                    cur_flow=e[edge[i]].c;                }            for(i=st;i!=end;i=e[edge[i]].to)            {                tmp=edge[i];                e[tmp].c-=cur_flow;                e[tmp^1].c+=cur_flow;            }            maxflow+=cur_flow;            u=neck;        }        for(i=edge[u];i!=-1;i=e[i].next)            if(e[i].c&&h[u]==h[e[i].to]+1)                break;        if(i!=-1)        {            edge[u]=i;            pre[e[i].to]=u;            u=e[i].to;        }        else         {            if(--numh[h[u]]==0)                break;            edge[u]=head[u];            for(tmp=n,i=head[u];i!=-1;i=e[i].next)                if(e[i].c)                    tmp=min(tmp,h[e[i].to]);            h[u]=tmp+1;            ++numh[h[u]];            if(u!=st)                u=pre[u];        }    }    return maxflow;}int v[maxn];void dfs(int r){    v[r]=1;    int i,k;    for(i=head[r];i!=-1;i=e[i].next)    {        k=e[i].to;        if(!v[k]&&e[i].c)        {            v[k]=1;            dfs(k);        }    }}int main(){    int i,n,m,s,u,p,a,b,res,num;    while(scanf("%d%d",&n,&m)!=EOF)    {        s=0;        u=2*n+1;        memset(head,0xff,sizeof(head));        tot=0;        for(i=1;i<=n;i++)        {            scanf("%d",&p);            add(i+n,u,p);            add(u,i+n,0);        }        for(i=1;i<=n;i++)        {            scanf("%d",&p);            add(s,i,p);            add(i,s,0);        }        while(m--)        {            scanf("%d%d",&a,&b);            add(a,b+n,INF);            add(b+n,a,0);        }        res=max_flow(s,u,n*2+1);        num=0;        clr(v);        dfs(s);        for(i=1;i<=n;i++)        {            if(!v[i])                num++;            if(v[i+n])                num++;        }        printf("%d\n%d\n",res,num);        for(i=1;i<=n;i++)        {            if(!v[i])                printf("%d -\n",i);            if(v[i+n])                printf("%d +\n",i);        }    }    return 0;}