題干：

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.

題目大意：

公司解雇員工，每個(gè)員工有一個(gè)權(quán)值，可正可負(fù)可為零（為正代表解雇員工可以獲得的利潤，為負(fù)代表獲得的利潤為負(fù)）。然后給出一些員工上下級(jí)的關(guān)系，如果解雇一個(gè)員工（比如經(jīng)理主管之類的），那么他手下的所有員工都會(huì)被解雇。注意一點(diǎn)：公司有很多部門，每個(gè)人可能不只效力于一個(gè)部門，所以有可能在這個(gè)部門A是B的上司，在另一個(gè)部門內(nèi)B是A的上司。（其實(shí)就是代表圖中可能有環(huán)）問對公司獲利最大的解雇計(jì)劃以及最少的解雇員工人數(shù)。

解題報(bào)告：

? 看起來就是個(gè)最大權(quán)閉合圖。但是不知道怎么證明這樣得到的就是最少的解雇人數(shù)了、、

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define F first #define S second #define ll long long #define pb push_back #define pm make_pair using namespace std; typedef pair<int,int> PII; const int MAX = 5e5 + 5; int n,m; int tot; const ll INF = 0x3f3f3f3f3f3f3f3f; struct Edge {int to,ne;ll w; } e[MAX]; int head[MAX]; int st,ed; ll a[MAX],dis[MAX]; int q[MAX];//一共多少個(gè)點(diǎn)跑bfs，dis數(shù)組和q數(shù)組就開多大。 void add(int u,int v,ll w) {e[++tot].to=v;e[tot].w=w;e[tot].ne=head[u];head[u]=tot; } bool bfs(int st,int ed) {memset(dis,-1,sizeof(dis));int front=0,tail=0;q[tail++]=st;dis[st]=0;while(front<tail) {int cur = q[front];if(cur == ed) return 1;front++;for(int i = head[cur]; i!=-1; i = e[i].ne) {if(e[i].w&&dis[e[i].to]<0) {q[tail++]=e[i].to;dis[e[i].to]=dis[cur]+1;}}}if(dis[ed]==-1) return 0;return 1; } ll dfs(int cur,ll limit) {//limit為源點(diǎn)到這個(gè)點(diǎn)的路徑上的最小邊權(quán) if(limit==0||cur==ed) return limit;ll w,flow=0;for(int i = head[cur]; i!=-1; i = e[i].ne) { if(e[i].w&&dis[e[i].to]==dis[cur]+1) {w=dfs(e[i].to,min(limit,e[i].w));e[i].w-=w;e[i^1].w+=w;flow+=w;limit-=w;if(limit==0) break;}}if(!flow) dis[cur]=-1;return flow; } ll dinic() {ll ans = 0;while(bfs(st,ed)) ans+=dfs(st,INF);//0x7fffffff可能就不對了？ return ans; } int ans2; bool vis[MAX]; void dfs2(int cur) {if(cur == ed) return;vis[cur] = 1;ans2++;for(int i = head[cur]; ~i; i = e[i].ne) {int v = e[i].to;if(e[i].w == 0 || vis[v]) continue;dfs2(v);} } int main() {cin>>n>>m;st=0;ed=n+1;tot=1;ll sum = 0;for(int i = 0; i<=n+1; i++) head[i] = -1;for(int i = 1; i<=n; i++) {scanf("%lld",a+i);if(a[i] > 0) sum += a[i],add(st,i,a[i]),add(i,st,0);if(a[i] < 0) add(i,ed,-a[i]),add(ed,i,0);}for(int a,b,i = 1; i<=m; i++) {scanf("%d%d",&a,&b);add(a,b,INF);add(b,a,0);}ll ans = sum - dinic();dfs2(st);printf("%d %lld\n",ans2-1,ans);return 0; }

玄學(xué)方法：

這題的特殊之處就是要輸出最少辭退員工數(shù)。
怎么辦呢？

利用一個(gè)經(jīng)典的trick:多關(guān)鍵字
建圖前，對所有b[i]，執(zhí)行變換b[i]=b[i]*10000-1，然后，會(huì)驚異地發(fā)現(xiàn)，
此時(shí)最大流所對應(yīng)的方案就是滿足辭退最少人數(shù)的了。
為什么？顯然，變換后的流量r2除以10000后再取整就等于原來的流量，但是
r2的后四位卻蘊(yùn)含了辭退人數(shù)的信息：每多辭退一個(gè)人，流量就會(huì)少1。

剩下的就是如何根據(jù)一個(gè)網(wǎng)絡(luò)流輸出方案。
我的做法：從源點(diǎn)開始沿著殘余網(wǎng)絡(luò)dfs（只走沒有滿載的邊），
能dfs到的點(diǎn)對應(yīng)的人就是需要辭退的。

int main() {cin>>n>>m;st=0;ed=n+1;tot=1;ll sum = 0;for(int i = 0; i<=n+1; i++) head[i] = -1;for(int i = 1; i<=n; i++) {scanf("%lld",a+i);a[i] = a[i]*10000-1;if(a[i] > 0) sum += a[i],add(st,i,a[i]),add(i,st,0);if(a[i] < 0) add(i,ed,-a[i]),add(ed,i,0);}for(int a,b,i = 1; i<=m; i++) {scanf("%d%d",&a,&b);add(a,b,INF);add(b,a,0);}ll ans = sum - dinic();dfs2(st);printf("%d %lld\n",ans2-1,(ans+9999)/10000);return 0; }

或者不用dfs2：

int main() {cin>>n>>m;st=0;ed=n+1;tot=1;ll sum = 0;for(int i = 0; i<=n+1; i++) head[i] = -1;for(int i = 1; i<=n; i++) {scanf("%lld",a+i);a[i] = a[i]*10000 - 1;if(a[i] > 0) sum += a[i],add(st,i,a[i]),add(i,st,0);if(a[i] < 0) add(i,ed,-a[i]),add(ed,i,0);}for(int a,b,i = 1; i<=m; i++) {scanf("%d%d",&a,&b);add(a,b,INF);add(b,a,0);}ll ans = sum - dinic(); // ans2 = -(ans % 10000 - 10000) % 10000 ;//這兩個(gè)用哪個(gè)都可以ans2 = (10000 - ans%10000)%10000 ;//別忘最后要%10000！！不然ans==10000的時(shí)候就WA了ans = (ans+ans2)/10000; // dfs2(st);printf("%d %lld\n",ans2,ans);return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的【POJ - 2987】Firing（最大权闭合图，网络流最小割，输出方案最小，放大权值法tricks）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。