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.

输入数据 1

3 6

1 2 3

4 2 1

1 2

1 1

3 2

1 2

3 1

2 3

输出数据 1

5

3

1 +

2 -

2 +

Source Northeastern Europe 2003, Northern Subregion

题目描述

Alice和Bob玩一个游戏。首先，Alice画一个有向图，包含N个顶点和M条弧。之后，Bob尝试破坏这个图。每次操作中，Bob可以选择任意一个顶点，并删除该顶点的所有入边或所有出边。

Alice为每个顶点设定了两个成本值：Wi+和Wi-。如果Bob删除第i个顶点的所有入边，他需要支付Wi+美元；如果删除所有出边，则需要支付Wi-美元。

要求计算Bob删除图中所有弧的最小总成本，并输出操作步骤。

输入格式

输入文件描述Alice所画的有向图。 第一行包含N和M（1 ≤ N ≤ 100，1 ≤ M ≤ 5000）。 第二行包含N个整数，表示Wi+。 第三行包含N个整数，表示Wi-。 所有成本均为正数且不超过10^6。 接下来的M行，每行包含两个整数，描述一条有向弧。图中可能包含自环和平行边。

输出格式

第一行输出W——Bob删除所有弧的最小总成本。 第二行输出K——Bob需要的操作次数。 接下来的K行，每行描述一个操作，包含顶点编号和'+'或'-'字符，用空格分隔。'+'表示删除该顶点的所有入边，'-'表示删除所有出边。

示例输入1

3 6

1 2 3

4 2 1

1 2

1 1

3 2

1 2

3 1

2 3

示例输出1

5

3

1 +

2 -

2 +

来源

Northeastern Europe 2003, Northern Subregion

算法标签

网络流/最小割，二分图匹配，顶点覆盖问题，Dinic算法

题意分析

Alice和Bob进行一个有向图删除游戏：

图结构：有向图包含N个顶点和M条弧（允许自环和平行边） 操作规则： 每次操作选择一个顶点，删除其所有入边（支付Wi+）或所有出边（支付Wi-） 目标是用最小成本删除所有边 输入输出： 输入：顶点数N、边数M，各顶点的Wi+和Wi-，以及所有边的信息 输出：最小总成本、操作次数及具体操作序列

解题思路

问题转化

将原问题转化为二分图最小点权覆盖问题： 将每个原始顶点拆分为两个顶点：一个负责入边（右侧），一个负责出边（左侧） 每条有向边u→v转化为从左u到右v的无限容量边

网络流建模

构建如下流网络： 源点S → 左侧顶点（容量Wi-）→ 原边（无限容量）→ 右侧顶点（容量Wi+）→ 汇点T

#include<iostream>
#include<cstring>
#include<stdio.h>
#include<algorithm>
#include<string>
#include<cmath>
#include<vector>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN=3010; // 点数的最大值
const int MAXM=400010; // 边数的最大值
#define captype int

struct SAP_MaxFlow{
    struct Edge{
        int from,to,next;
        captype cap;
    }edges[MAXM];
    int tot,head[MAXN];
    int gap[MAXN];
    int dis[MAXN];
    int cur[MAXN];
    int pre[MAXN];

    void init(){
        tot=0;
        memset(head,-1,sizeof(head));
    }
    void AddEdge(int u,int v,captype c,captype rc=0){
        edges[tot].from = u;
        edges[tot].to = v;
        edges[tot].cap = c;
        edges[tot].next = head[u];
        head[u]=tot++;
        
        edges[tot].from = v;
        edges[tot].to = u;
        edges[tot].cap = rc;
        edges[tot].next = head[v];
        head[v]=tot++;
    }
    captype maxFlow_sap(int sNode,int eNode, int n){
        memset(gap,0,sizeof(gap));
        memset(dis,0,sizeof(dis));
        memcpy(cur,head,sizeof(head));
        pre[sNode] = -1;
        gap[0]=n;
        captype ans=0;
        int u=sNode;
        while(dis[sNode]<n){
            if(u==eNode){
                captype Min=INF;
                int inser;
                for(int i=pre[u]; i!=-1; i=pre[edges[i^1].to])
                if(Min>edges[i].cap){
                    Min=edges[i].cap;
                    inser=i;
                }
                for(int i=pre[u]; i!=-1; i=pre[edges[i^1].to]){
                    edges[i].cap-=Min;
                    edges[i^1].cap+=Min;
                }
                ans+=Min;
                u=edges[inser^1].to;
                continue;
            }
            bool flag = false;
            int v;
            for(int i=cur[u]; i!=-1; i=edges[i].next){
                v=edges[i].to;
                if(edges[i].cap>0 && dis[u]==dis[v]+1){
                    flag=true;
                    cur[u]=pre[v]=i;
                    break;
                }
            }
            if(flag){
                u=v;
                continue;
            }
            int Mind= n;
            for(int i=head[u]; i!=-1; i=edges[i].next)
            if(edges[i].cap>0 && Mind>dis[edges[i].to]){
                Mind=dis[edges[i].to];
                cur[u]=i;
            }
            gap[dis[u]]--;
            if(gap[dis[u]]==0) return ans;
            dis[u]=Mind+1;
            gap[dis[u]]++;
            if(u!=sNode) u=edges[pre[u]^1].to;
        }
        return ans;
    }
}F;

int vis[MAXN];
void dfs(int u)
{
    vis[u] = 1;
    for(int i=F.head[u];~i;i=F.edges[i].next){
        int v= F.edges[i].to;
        if(!vis[v] && F.edges[i].cap>0){
            dfs(v);
        }
    }
}

int main()
{
    #ifndef ONLINE_JUDGE
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int N,M;
    int u,v,tmp;
    while(scanf("%d %d",&N, &M)==2){
        F.init();
        int s = 0, t = 2*N+1;
        
        // 读入W+并建边
        for(int i=1;i<=N;++i){
            scanf("%d",&tmp);
            F.AddEdge(N+i,t,tmp); // 右边点连汇点
        }
        
        // 读入W-并建边
        for(int i=1;i<=N;++i){
            scanf("%d",&tmp);
            F.AddEdge(s,i,tmp); // 源点连左边点
        }
        
        // 读入边
        for(int i=1;i<=M;++i){
            scanf("%d %d",&u, &v);
            F.AddEdge(u,N+v,INF); // 左边点连右边点
        }
        
        int flow = F.maxFlow_sap(s,t,t+1);
        
        // 找割集
        memset(vis,0,sizeof(vis));
        dfs(s);
        
        vector<pair<int,char> > res;
        
        // 检查左边点(1~N)
        for(int i=1;i<=N;++i){
            if(!vis[i]){ // 在S集
                res.push_back(make_pair(i,'-')); // 修改：使用make_pair
            }
        }
        
        // 检查右边点(N+1~2N)
        for(int i=N+1;i<=2*N;++i){
            if(vis[i]){ // 在T集
                res.push_back(make_pair(i-N,'+')); // 修改：使用make_pair
            }
        }
        
        printf("%d\n%d\n",flow,(int)res.size());
        for(int i = 0; i < res.size(); i++){ // 修改：使用传统for循环
            printf("%d %c\n",res[i].first,res[i].second);
        }
    }
    return 0;
}