Destroying The Graph

Description

Alice and Bob play the following game. First, Alice draws some directed graph with N vertices and M arcs. After that Bob tries to destroy it. In a move he may take any vertex of the graph and remove either all arcs incoming into this vertex, or all arcs outgoing from this vertex.
Alice assigns two costs to each vertex: Wi+ and Wi-. If Bob removes all arcs incoming into the i-th vertex he pays Wi+ dollars to Alice, and if he removes outgoing arcs he pays Wi- dollars.
Find out what minimal sum Bob needs to remove all arcs from the graph.

Input

Input file describes the graph Alice has drawn. The first line of the input file contains N and M (1 <= N <= 100, 1 <= M <= 5000). The second line contains N integer numbers specifying Wi+. The third line defines Wi- in a similar way. All costs are positive and do not exceed 106 . Each of the following M lines contains two integers describing the corresponding arc of the graph. Graph may contain loops and parallel arcs.

Output

On the first line of the output file print W --- the minimal sum Bob must have to remove all arcs from the graph. On the second line print K --- the number of moves Bob needs to do it. After that print K lines that describe Bob's moves. Each line must first contain the number of the vertex and then '+' or '-' character, separated by one space. Character '+' means that Bob removes all arcs incoming into the specified vertex and '-' that Bob removes all arcs outgoing from the specified vertex.

Sample Input

3 6
1 2 3
4 2 1
1 2
1 1
3 2
1 2
3 1
2 3

Sample Output

5
3
1 +
2 -
2 +
题意：对每个点可以选择删除它的所有入边，也可以选择删除它所有出边，每个点的每种删除方法会消耗不同的钱。
问：用最少的钱删掉所有边并输出一个删除方案。
分析：对每个点有两种操作，一种是删除它所有入边，消费是x，另一种是删除它所有出边，消费是y。将每个点拆成两个点u1，u2。s到u1为删除点所有出边的花费，u2到t为删除点所有入边的花费。对图中的每条边（u，v),有u1到v2是正无穷。即一个二分图再加上源跟汇，最大流即为最小费用。
题目要求输出方案，对每个点，如果u1在割中，则u有一个删出边的操作，如果u2在割中，则u有一个删除入边的操作。
如何判断点在s临边的个还是t临边的割。在二分图里，从s能到达的最后一个点与t成一最小割，如果s是不能到达的点，则s与该点成一最小割。所以最小割不能简单的认为是流路中容量最小的边，因为会有容量最小且相等的。在二分图结构里，因为每个流路只有三条边，可能会出现s->u->v->t，而u->v是容量无穷的，所以不会成个最小割，如果s->u跟v->t容量一样小，则可认为最小割是任选一个。对于任意图，一个流路会出现多条边容量一样是最小的。这种情况下会有s->a->b->c->d->e->...->t。则第一个满流量的或者最后一个满流量的边是最小割。其实二分图的最小割也是满足这个说法。
代码：
#include <stdio.h>  
#include <string.h> 
#include <queue> 
#include <algorithm>
#include <iostream>
#define Min(a, b) (a) < (b) ? a : b  
#define Max(a, b) (a) > (b) ? a : b
using  namespace std;  
const  int MAXN = 2005;  
const  int MAXM = 700000;  
const  int INF = 1100000000;  
struct  Edge  
{  
    int  st, ed;  
    int  next;  
    int  flow; 
    int cap; 
}edge[MAXM]; 
int  head[MAXN], level[MAXN], que[MAXN], E;
void add(int u, int v, int w)  
{  
    edge[E].flow = 0;  
    edge[E].cap = w;
    edge[E].st = u;  
    edge[E].ed = v;  
    edge[E].next = head[u];  
    head[u] = E++;      
    edge[E].flow = 0; 
    edge[E].cap = 0; 
    edge[E].st = v;  
    edge[E].ed = u;  
    edge[E].next = head[v];  
    head[v] = E++;  
}
int dinic_bfs(int src, int dest, int ver)        
{        
    int i, j;         
    for (i = 0; i <= ver; i++)
    {    
        level[i] = -1;
    }
    int rear = 1;        
    que[0] = src; level[src] = 0;        
    for(i = 0; i < rear; i++) 
    {        
          for(j = head[que[i]]; j != -1; j = edge[j].next)
         {        
            if(level[edge[j].ed] == -1 && edge[j].cap > edge[j].flow)        
            {        
              level[edge[j].ed] = level[que[i]]+1;        
              que[rear++] = edge[j].ed;        
            }
         }
    }
    return  level[dest] >= 0;        
}        
     
int dinic_dfs(int src, int dest, int ver)        
{        
    int stk[MAXN], top = 0;        
    int ret = 0, cur, ptr, pre[MAXN], minf, i;        
    int del[MAXN];        
    for (i = 0; i <= ver; i++) 
    {
        del[i] = 0;
    }
    stk[top++] = src;         
    pre[src] = src; 
    cur = src;        
    while(top)        
    {        
        while(cur != dest && top)        
        {        
            for(i = head[cur]; i != -1; i = edge[i].next)        
            {        
                if(level[edge[i].ed] == level[cur] + 1 && edge[i].cap > edge[i].flow  && !del[edge[i].ed])        
                {        
                    stk[top++] = edge[i].ed;      
                    cur = edge[i].ed;        
                    pre[edge[i].ed] = i;                       
                    break;     
                }        
            }     
            if(i == -1)       
            {        
                del[cur] = 1;        
                top--;        
                if(top) cur = stk[top-1];        
            }        
        }                
        if(cur == dest)        
        {       
            minf = INF;        
            while(cur != src)        
            {        
                cur = pre[cur];        
                if(edge[cur].cap - edge[cur].flow < minf) minf = edge[cur].cap - edge[cur].flow;        
                cur = edge[cur].st;        
            }
            cur = dest;        
            while(cur != src)        
            {        
                cur = pre[cur];        
                edge[cur].flow += minf;        
                edge[cur^1].flow -= minf;        
                if(edge[cur].cap - edge[cur].flow == 0)
                {
                     ptr = edge[cur].st;
                }
                cur = edge[cur].st;        
            }        
            while(top > 0&& stk[top-1] != ptr) top--;        
            if(top)  cur = stk[top-1];        
            ret += minf;      
        }        
    }        
    return ret;        
}        
int Dinic(int src, int dest, int ver)        
{        
    int  ret = 0, t;        
    while(dinic_bfs(src, dest, ver))        
    {        
        t = dinic_dfs(src, dest, ver);        
        if(t) ret += t;        
        else  break;        
    }        
    return ret;        
}
int visit[MAXN];
void dfs(int u)
{
    visit[u] = 1;
    int i;
    for (i = head[u]; i != -1; i = edge[i].next)
    {
        if (!visit[edge[i].ed] && edge[i].cap > edge[i].flow)
        {
            visit[edge[i].ed] = 1;
            dfs(edge[i].ed);
        }
    }
}
int main()
{
    int n, m, i, u, v, w;
    scanf("%d%d", &n, &m);
    int s = 0, t = n + n + 1, ver = t + 1;
    E = 0;
    for (i = 0; i <= ver; i++)
    {
        head[i] = -1;
    }
    for (i = 1; i <= n; i++)
    {
        scanf("%d", &w);
        add(i + n, t, w); 
    }
    for (i = 1; i <= n; i++)
    {
        scanf("%d", &w);
        add(0, i, w);
    }
    while (m--)
    {
        scanf("%d%d", &u, &v);
        add(u, v + n, INF);
    }
    int ans = Dinic(s, t, ver);
    for (i = 0; i <= ver; i++)
    {
        visit[i] = 0;
    }
    dfs(s);
    int num = 0;
    for (i = 1; i <= n; i++)
    {
        if (visit[i + n]) num++;
        if (!visit[i]) num++;
    }
    printf("%d\n%d\n", ans, num);
    for (i = 1; i <= n; i++)
    {
        if (visit[i + n])
        {
            printf("%d +\n", i);
        }
        if (!visit[i])
        {
            printf("%d -\n", i); 
        }
    }
    return 0;
}
/*
3 2
2 1 1
3 1 3
2 1
3 1


3 2
3 1 1
3 1 3
2 1
3 1


3 2
3 1 1
3 1 2
2 1
3 1

3 2
3 1 1
3 1 1
2 1
3 1

2 1
1 1
1 1
1 2

*/