POJ 2987: Firing

3715 ワード

ACM_図説

タイトルリンク:http://poj.org/problem?id=2987
标题:今は一群の人がいて、一人一人を除名すると相応の収益があります(プラスとマイナス).
彼らの間の上下関係も与えられ、一人を除名すれば部下を除名しなければならない.そして部下の部下を順次類推しなければならない.
最大収益の値と最大収益を保証する前提の下で少なくとも何人を除名します.
アルゴリズム:
図の最大重みのある閉じたサブ図、すなわち閉じた図内の任意の点の任意の後続も必ず閉じた図にある.
Amberの「最小割モデルの情報学コンテストでの応用」では、非常に明確に説明されています.
Sから各ポイントにエッジを作成し、重み値はそのポイントの重み値の絶対値です.このポイント重み値が負の場合、そのポイントからTにエッジが作成され、重み値はそのポイント重み値の絶対値となる.
エッジ(u,v)が存在する場合、uからvまでのエッジが構築され、流量は無限大である.
最大収益は、正の重み点の重み値と-最小割S割集が最大の重み閉合子図の点、すなわち除名されるべき人である.
コード:

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define INF 0x3f3f3f3f
using namespace std;

const int maxn = 10000;
const int maxm = 1000000;

int to[maxm], nxt[maxm];
long long cap[maxm];
int head[maxn], cur[maxn], Q[maxn], dep[maxn];
int E;

void _addedge(int u, int v, long long w)
{
    to[E] = v;
    cap[E] = w;
    nxt[E] = head[u];
    head[u] = E ++;
}

void addedge(int u, int v, long long w)
{
    _addedge(u, v, w);
    _addedge(v, u, 0);
}

bool bfs(int S, int T)
{
    memset(dep, -1, sizeof(dep));
    dep[T] = 0;
    int front = 0, rear = 0;
    Q[rear ++] = T;
    while (front != rear && dep[S] == -1)
    {
       int u = Q[front ++];
       for (int i = head[u]; i != -1; i = nxt[i])
        {
            int v = to[i];
            if (cap[i ^ 1] && dep[v] == -1)
            {
                dep[v] = dep[u] + 1;
                Q[rear ++] = v;
            }
        }
    }
    return dep[S] != -1;
}

long long dfs(int S, int T, long long lim)
{
    if (S == T)
    {
        return lim;
    }
    long long tmp = lim;
    for (int &i = cur[S]; i != -1; i = nxt[i])
    {
        int v = to[i];
        if (cap[i] && dep[S] == dep[v] + 1)
        {
            int ret = dfs(v, T, min(tmp, cap[i]));
            tmp -= ret;
            cap[i] -= ret;
            cap[i ^ 1] += ret;
        }
        if (!tmp)
        {
            break;
        }
    }
    return lim - tmp;
}

long long dinic(int S, int T, int n)
{
    long long ans = 0;
    while (bfs(S, T))
    {
        for (int i = 0; i < n; i ++)
        {
            cur[i] = head[i];
        }
        ans += dfs(S, T, INT_MAX);
    }
    return ans;
}

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

int dfs(int u)
{
    int cot = 1;
    for (int i = head[u]; i != -1; i = nxt[i])
    {
        int v = to[i];
        if (dep[v] == -1 && cap[i])
        {
            dep[v] = dep[u] + 1;
            cot += dfs(v);
        }
    }
    return cot;
}

int main()
{
    int n, m;
    while (scanf("%d %d", &n, &m) == 2)
    {
        long long sum = 0;
        init();
        int S = 0, T = n + 1;
        for (int i = 1; i <= n; i ++)
        {
            long long bonus;
            scanf("%lld", &bonus);
            if (bonus > 0)
            {
                addedge(S, i, bonus);
                sum += bonus;
            }
            else
            {
                addedge(i, T, -bonus);
            }
        }
        while (m --)
        {
            int u, v;
            scanf("%d %d", &u, &v);
            addedge(u, v, INF);
        }
        long long flow = dinic(S, T, n + 2);
        memset(dep, -1, sizeof(dep));
        dep[0] = 0;
        printf("%d %lld
", dfs(0) - 1, sum - flow);
    }
    return 0;
}

Webページ共通JavaScriptコード

hdu 1426 Sudoku Killerが泣かせてくれたDFS