程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> POJ 2125 最小割最大流

POJ 2125 最小割最大流

編輯：C++入門知識

Destroying The Graph Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 6732 Accepted: 2120 Special Judge

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 10⁶ . 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

Sample Output

題意:給定一個圖，給出刪除某一個點入邊，出邊的費用，要求用最小的費用刪除掉所有的邊，

要刪除所有的邊，對於每一個點，要麼刪除其入邊，要麼刪除其出邊，兩個操作一定要執行一個，很顯然是一個最小點權覆蓋，

添加一個源點，一個匯點，把每一個點拆點，假如刪除入邊，則相當於保留出邊，出點向匯點連邊，刪除出邊，則保留入邊，

源點向入點連邊，對於每一條給定的邊，起點的入點向終點的出點連邊，求出的最大流就是最小費用，這時候圖已經被分為兩部分，然後在殘圖上dfs標記，

就可以找到操作方案。

代碼：

/* ***********************************************
Author :rabbit
Created Time :2014/3/8 16:40:10
File Name :1718.cpp
************************************************ */
#pragma comment(linker, "/STACK:102400000,102400000")
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define INF 0x3f3f3f3f
#define eps 1e-5
#define pi acos(-1.0)
typedef long long ll;
const int maxn=100010;
const int maxm=400010;
struct Edge{
    int to,next,cap,flow;
    Edge(){};
    Edge(int _next,int _to,int _cap,int _flow){
        next=_next;to=_to;cap=_cap;flow=_flow;
    }
}edge[maxm];
int head[maxn],tol,gap[maxn],dep[maxn],cur[maxn];
void addedge(int u,int v,int flow){
    edge[tol]=Edge(head[u],v,flow,0);head[u]=tol++;
    edge[tol]=Edge(head[v],u,0,0);head[v]=tol++;
}
int Q[maxn];
void bfs(int start,int end){
    memset(dep,-1,sizeof(dep));
    memset(gap,0,sizeof(gap));
    gap[0]++;int front=0,rear=0;
    dep[end]=0;Q[rear++]=end;
    while(front!=rear){
        int u=Q[front++];
        for(int i=head[u];i!=-1;i=edge[i].next){
            int v=edge[i].to;if(dep[v]==-1&&edge[i].cap)
                Q[rear++]=v,dep[v]=dep[u]+1,gap[dep[v]]++;
        }
    }
}
int S[maxn];
int sap(int start,int end,int N){
    bfs(start,end);
    memcpy(cur,head,sizeof(head));
    int top=0,u=start,ans=0;
    while(dep[start]edge[S[i]].cap-edge[S[i]].flow)
                    MIN=edge[S[i]].cap-edge[S[i]].flow,id=i;
            for(int i=0;i