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

*/