「模闆」·[最小割]最小點權覆寫——POJ 2125 Destroying The Graph

• 題目連結：http://poj.org/problem?id=2125
• 題意：給你一個n個點m條邊的有向帶環圖，問删除所有的邊的最小代價。删邊的操作：選擇一個點，删掉所有進入該點的有向邊，支付wi，或删掉所有從該點出去的邊，支付wo。并輸出方案。
• 思路：由題意需要删除所有邊，是以為最小點權覆寫。由于删除進入/出去的有向邊的代價不同，是以要拆點。将n個點拆稱2×n個，變成一個二分圖，将原圖中從u連向v的邊在二分圖中建成從u連向v+n，權值為INF，是以s連到點1～n賦予從該點出去的權值，（n+1)～2×n 連到t賦予進入該點的權值。
• 補充知識點
  • 最小點權覆寫：-> 最小割 -> 最大流。從超級源點 s 周遊殘餘網絡，如果 不能 周遊到1～n（賦予了出去的權值），則說明删除了這些點的出邊，如果 可以 周遊到 (n+1)～2*n ，說明删除了這些點的入邊。

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <math.h>
#define pi acos(-1)
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
const int INF = 0x3f3f3f3f;
const LL LL_INF = 0x3f3f3f3f3f3f3f3f;
const int maxn = 100 + 10;
const int maxm = 5000 + 10;
const int maxv = maxn * 2;
const int maxe = maxm * 2;
const int mod = 1e9 + 7;

int wi[maxv], wo[maxv];

//

int s, t;
int head[maxe], tot=0, nowedge[maxe];
int dis[maxv];
int vis[maxv];
int n, f, d;

struct Edge
{
    int to, next, cap;
}es[maxe];

int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

void init()
{
    memset(head, -1, sizeof(head));
    memset(vis, 0, sizeof(vis));
    tot=0;
}

void add(int u, int v, int vol)
{
    es[tot].to = v;
    es[tot].cap = vol;
    es[tot].next = head[u];
    head[u] = tot++;

    es[tot].to = u;
    es[tot].cap = 0;
    es[tot].next = head[v];
    head[v] = tot++;
}

bool BFS()
{
    queue<int> que;
    memset(dis, -1, sizeof(dis));
    dis[s] = 0;
    que.push(s);
    int cur, v;
    while(!que.empty())
    {
        cur = que.front(); que.pop();
        for(int i=head[cur]; i!=-1; i=es[i].next){
            v = es[i].to;
            if(dis[v]==-1 && es[i].cap>0){
                dis[v] = dis[cur]+1;
                que.push(v);
            }
        }
    }
    if(dis[t] == -1) return false;
    else return true;
}

LL DFS(int cur, LL low)
{
    LL res=0, add=0;// 多路增廣
    if(cur == t) return low;
    for(int i=nowedge[cur]; i!=-1; i=es[i].next){
        nowedge[cur] = i;
        if(dis[es[i].to]==dis[cur]+1
        && es[i].cap>0
        && (add = DFS(es[i].to, min(low, (LL)es[i].cap))) ){
            es[i].cap -= add;
            es[i^1].cap += add;
            low -= add;
            res += add;
            if(low == 0) break;
        }
    }
    if(res == 0) dis[cur] = 0;
    return res;
}

LL MAXFLOW()
{
    LL ans=0 , tmp=0;
    while(BFS()){
        for(int i=s; i<=t; i++){
            nowedge[i] = head[i];
        }
        if(tmp = DFS(s, INF))
            ans += tmp;
    }
    return ans;
}


int left_net(int cur)
{
    vis[cur] = 1;
    int ans = 1;
    for(int i=head[cur]; i!=-1; i = es[i].next){
        if(es[i].cap > 0 && !vis[es[i].to]) ans += left_net(es[i].to);
    }
    return ans;
}

int main()
{

    int n, m;
    n = read(); m = read();
    init();
    s = 0;
    t = 2*n+1;

    for(int i=1; i<=n; i++){
        wi[i] = read();
        add(i+n, t, wi[i]);  // 因為建原圖裡的邊時，i+n是作為進入的點，所有賦予進入的權值
    }
    for(int i=1; i<=n; i++){
        wo[i] = read();
        add(s, i, wo[i]);    // 因為建原圖裡的邊時，i是作為出去的點，所有賦予出去的權值
    }
    int u, v;
    for(int i=1; i<=m; i++){
        u = read(); v = read();
        add(u, v+n, INF);    // 建原圖裡的邊
    }

    printf("%lld\n", MAXFLOW());
    left_net(s);
    int cnt=0;
    for(int i=1; i<=n; i++){
        if(!vis[i]) cnt++;
        if(vis[i+n]) cnt++;
    }
    printf("%d\n", cnt);
    for(int i=1; i<=n; i++){
        if(!vis[i]) printf("%d -\n", i);
        if(vis[i+n]) printf("%d +\n", i);
    }
    return 0;


}