poj - 2987 - Firing（最大權閉合圖）

poj - 2987 - Firing（最大權閉合圖）

題意：n(0 < n ≤ 5000)個人，m(0 ≤ m ≤ 60000)個上下級關系，炒一個人可以獲得收益或者損失bi (|bi| ≤ 10 ^ 7, 1 ≤ i ≤ n)，炒一個人會把他的所有下級一起炒掉，問怎樣炒人使收益最大，輸出最大收益和最少炒人的數量。

題目鏈接：http://poj.org/problem?id=2987

——>>炒一個人會把他的所有下級一起炒掉，這時存在依賴關系，對應圖論中的閉合圖。。最大收益對應最大權和。。於是，最大權閉合圖上場。。

最少炒人數？獲得最大收益的方案可能有多種嗎？其實不然，假設方案一與方案二都獲得最大收益，那麼，可以把兩個方案中所炒的人都炒了，這時的收益肯定更大，說明方案一、二還不是最優的，與假設矛盾。。因此，獲得最大收益的方案只有一種。。

建圖（超級源S = 0，超級匯T = n + 1）：

1）對於炒掉他可以正收益的人i: S -> i（bi）

2）對於炒掉他會損失的人i: i -> T（-bi）

3）依賴關系 i 的下級是 j，i -> j（INF）

最大權閉合圖可以轉化為最小割求解，最小割轉化為最大流求解。。於是，Dinic上場。。

怎麼求出被炒的人呢？ 在跑完最大流後，殘量網絡中S到他們或者他們之間肯定不滿流，如果滿流，就屬於割，不應炒他。。於是，dfs吧。。

#include 
#include 
#include 
#include 

using std::queue;
using std::min;

const int MAXN = 5000 + 10;
const int MAXM = 60000 + MAXN + 10;
const int INF = 0x3f3f3f3f;

int n, m, numberOfFire;
long long sum, maxProfit;
int S, T;
int hed[MAXN], ecnt;
int h[MAXN], cur[MAXN];
bool vis[MAXN];

struct EDGE
{
    int to;
    int cap;
    int flow;
    int nxt;
} edge[MAXM << 1];

void Init()
{
    ecnt = 0;
    memset(hed, -1, sizeof(hed));
    sum = 0;
}

void AddEdge(int u, int v, int cap)
{
    edge[ecnt].to = v;
    edge[ecnt].cap = cap;
    edge[ecnt].flow = 0;
    edge[ecnt].nxt = hed[u];
    hed[u] = ecnt++;
    edge[ecnt].to = u;
    edge[ecnt].cap = 0;
    edge[ecnt].flow = 0;
    edge[ecnt].nxt = hed[v];
    hed[v] = ecnt++;
}

bool Bfs()
{
    memset(h, -1, sizeof(h));
    queue qu;
    qu.push(S);
    h[S] = 0;

    while (!qu.empty())
    {
        int u = qu.front();
        qu.pop();
        for (int e = hed[u]; e != -1; e = edge[e].nxt)
        {
            int v = edge[e].to;
            if (h[v] == -1 && edge[e].cap > edge[e].flow)
            {
                h[v] = h[u] + 1;
                qu.push(v);
            }
        }
    }

    return h[T] != -1;
}

int Dfs(int u, int cap)
{
    if (u == T || cap == 0) return cap;

    int flow = 0, subFlow;

    for (int e = hed[u]; e != -1; e = edge[e].nxt)
    {
        int v = edge[e].to;
        if (h[v] == h[u] + 1 && (subFlow = Dfs(v, min(cap, edge[e].cap - edge[e].flow))) > 0)
        {
            flow += subFlow;
            edge[e].flow += subFlow;
            edge[e ^ 1].flow -= subFlow;
            cap -= subFlow;
            if (cap == 0) break;
        }
    }

    return flow;
}

long long Dinic()
{
    long long maxFlow = 0;

    while (Bfs())
    {
        memcpy(cur, hed, sizeof(hed));
        maxFlow += Dfs(S, INF);
    }

    return maxFlow;
}

void Read()
{
    int cap, up, under;

    S = 0;
    T = n + 1;
    for (int i = 1; i <= n; ++i)
    {
        scanf("%d", &cap);
        if (cap > 0)
        {
            AddEdge(S, i, cap);
            sum += cap;
        }
        else
        {
            AddEdge(i, T, -cap);
        }
    }
    while (m--)
    {
        scanf("%d%d", &up, &under);
        AddEdge(up, under, INF);
    }
}

void GetMaxProfit()
{
    maxProfit = sum - Dinic();
}

void FireDfs(int u)
{
    vis[u] = true;
    numberOfFire++;
    for (int e = hed[u]; e != -1; e = edge[e].nxt)
    {
        int v = edge[e].to;
        if (!vis[v] && edge[e].flow < edge[e].cap)
        {
            FireDfs(v);
        }
    }
}

void GetFireCnt()
{
    numberOfFire = 0;
    memset(vis, 0, sizeof(vis));
    FireDfs(S);
    numberOfFire--;
}

void Output()
{
    printf("%d %I64d\n", numberOfFire, maxProfit);
}

int main()
{
    while (scanf("%d%d", &n, &m) == 2)
    {
        Init();
        Read();
        GetMaxProfit();
        GetFireCnt();
        Output();
    }

    return 0;
}