poj 2987 Firing 最大權閉合子圖

Firing

Time Limit: 5000MS	Memory Limit: 131072K
Total Submissions: 8952	Accepted: 2690

Description

You’ve finally got mad at “the world’s most stupid” employees of yours and decided to do some firings. You’re now simply too mad to give response to questions like “Don’t you think it is an even more stupid decision to have signed them?”, yet calm enough to consider the potential profit and loss from firing a good portion of them. While getting rid of an employee will save your wage and bonus expenditure on him, termination of a contract before expiration costs you funds for compensation. If you fire an employee, you also fire all his underlings and the underlings of his underlings and those underlings’ underlings’ underlings… An employee may serve in several departments and his (direct or indirect) underlings in one department may be his boss in another department. Is your firing plan ready now?

Input

The input starts with two integers n (0 < n ≤ 5000) and m (0 ≤ m ≤ 60000) on the same line. Next follows n + m lines. The first n lines of these give the net profit/loss from firing the i-th employee individually bi (|bi| ≤ 107, 1 ≤ i ≤ n). The remaining m lines each contain two integers i and j (1 ≤ i, j ≤ n) meaning the i-th employee has the j-th employee as his direct underling.

Output

Output two integers separated by a single space: the minimum number of employees to fire to achieve the maximum profit, and the maximum profit.

Sample Input

5 5
8
-9
-20
12
-10
1 2
2 5
1 4
3 4
4 5      

Sample Output

2 2      

Hint

As of the situation described by the sample input, firing employees 4 and 5 will produce a net profit of 2, which is maximum.   連結： http://poj.org/problem?id=2987 最大權閉合圖裸題。   最大權閉合圖 參考 胡伯濤 算法合集之《最小割模型在資訊學競賽中的應用》   閉合圖（closure）：是有向圖點一個點集，且 該點集的所有出邊都還指向該點集。即閉合圖點任意點點任意後繼也一定在閉合圖中。 最大權閉合圖(maximum weight closure)：是一個點權之和最大點閉合圖。 閉合圖點性質恰好反映來事件間點必要條件的關系。   閉合圖問題建圖方法： 在原圖點集的基礎上增加源s和彙t,對于原圖中點每條邊(u,v),在圖中連接配接u,v點，容量為正無窮。 對于權值為正的點。連接配接源s和該點,容量為該點的權值。 對于權值為負點點。連接配接彙t和該點。容量為該點的權值。 最大權值 = 所有正權值之和 - 最小割   hdu 3061 Battle http://acm.hdu.edu.cn/showproblem.php?pid=3061 和這題一樣  

1 #include <iostream>
  2 #include <cstring>
  3 #include <cstdio>
  4 #include <cmath>
  5 #include <string>
  6 #include <queue>
  7 #include <vector>
  8 using namespace std;
  9 #define maxn 5010
 10 const int inf = 0x3f3f3f3f;
 11 struct Edge
 12 {
 13     int from, to, cap, flow;
 14     Edge(int f, int t, int c, int fl)
 15     {
 16         from = f; to = t; cap = c; flow = fl;
 17     }
 18 };
 19 vector <Edge> edges;
 20 vector <int> G[maxn];
 21 int vis[maxn], d[maxn], cur[maxn];
 22 int s, t, n, m;
 23 long long min(long long a, long long b)
 24 {
 25     return a<b?a:b;
 26 }
 27 void AddEdge(int from, int to, int cap)
 28 {
 29     edges.push_back(Edge(from, to, cap, 0));
 30     edges.push_back(Edge(to, from, 0, 0));
 31     m = edges.size();
 32     G[from].push_back(m-2);
 33     G[to].push_back(m-1);
 34 }
 35 bool bfs()
 36 {
 37     memset(vis, 0, sizeof(vis));
 38     d[s] = 0;
 39     vis[s] = 1;
 40     queue <int> q;
 41     q.push(s);
 42     while(!q.empty())
 43     {
 44         int u = q.front(); q.pop();
 45         for(int i = 0; i < G[u].size(); i++)
 46         {
 47             Edge &e = edges[G[u][i]];
 48             if(!vis[e.to] && e.cap > e.flow)
 49             {
 50                 vis[e.to] = 1;
 51                 d[e.to] = d[u]+1;
 52                 q.push(e.to);
 53             }
 54         }
 55     }
 56     return vis[t];
 57 }
 58 long long dfs(int x, long long a)
 59 {
 60     if(x == t || a == 0) return a;
 61     long long flow = 0, f;
 62     for(int &i = cur[x]; i < G[x].size(); i++)
 63     {
 64         Edge &e = edges[G[x][i]];
 65         if(d[x]+1 == d[e.to] && (f = dfs(e.to, min(a, e.cap - e.flow))) > 0)
 66         {
 67             e.flow += f;
 68             edges[G[x][i]^1].flow -= f;
 69             flow += f;
 70             a -= f;
 71             if(a == 0) break;
 72         }
 73     }
 74     return flow;
 75 }
 76 long long Maxflow()
 77 {
 78     long long flow = 0;
 79     while(bfs())
 80     {
 81         memset(cur, 0, sizeof(cur));
 82         flow += dfs(s, inf);
 83     }
 84     return flow;
 85 }
 86 int N, M;
 87 int main()
 88 {
 89     while(~scanf("%d%d",  &N, &M))
 90     {
 91         edges.clear();
 92         for(int i = 0; i <= N+1; i++) G[i].clear();
 93         s = 0; t = N+1;
 94         long long sum = 0;
 95         for(int i = 1; i <= N; i++)
 96         {
 97             long long  temp; scanf("%lld", &temp);
 98             if(temp > 0) {AddEdge(s, i, temp); sum += temp;}
 99             else if(temp < 0) AddEdge(i, t, -temp);
100         }
101         for(int i = 1; i <= M; i++)
102         {
103             int a, b; scanf("%d%d", &a, &b);
104             AddEdge(a, b, inf);
105         }
106         sum -= Maxflow();
107         int ans = 0;
108         for(int i = 1; i <= N; i++)
109         {
110             if(vis[i]) ans++;
111         }
112         printf("%d %lld\n", ans, sum);
113     }
114     return 0;
115 }      

轉載于:https://www.cnblogs.com/titicia/p/4699753.html