Problem 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

題意：有 n 個人，每個人有一個價值，現在這 n 個人中有 m 個關系 x y，表示 y 是 x 的下級，現在要進行裁員，裁掉一個員工后，也會將他的下級裁掉，現在要求裁掉若干人，使得獲得的價值最大，問裁掉的人數與價值

思路：最大權閉合子圖裸題

首先記錄整個圖中所有正點權之和，然后建圖

設一個超級源點 S 與一個超級匯點 T，從源點 S 向每個正權點連一條容量為權值的邊，每個負權點向匯點 T 連一條容量為權值的絕對值的邊，原圖中的邊容量均設為 INF

在建完圖后，利用 Dinic 求最小割，最終人數是最小割中的元素個數，價值是正權值之和-最小割的值

注意使用 long long

Source Program

#include<iostream> #include<cstdio> #include<cstdlib> #include<string> #include<cstring> #include<cmath> #include<ctime> #include<algorithm> #include<utility> #include<stack> #include<queue> #include<vector> #include<set> #include<map> #include<bitset> #define PI acos(-1.0) #define INF 0x3f3f3f3f #define LL long long #define Pair pair<LL,LL> LL quickPow(LL a,LL b){ LL res=1; while(b){if(b&1)res*=a; a*=a; b>>=1;} return res; } LL multMod(LL a,LL b,LL mod){ a%=mod; b%=mod; LL res=0; while(b){if(b&1)res=(res+a)%mod; a=(a<<=1)%mod; b>>=1; } return res%mod;} LL quickPowMod(LL a, LL b,LL mod){ LL res=1,k=a; while(b){if((b&1))res=multMod(res,k,mod)%mod; k=multMod(k,k,mod)%mod; b>>=1;} return res%mod;} LL getInv(LL a,LL mod){ return quickPowMod(a,mod-2,mod); } LL GCD(LL x,LL y){ return !y?x:GCD(y,x%y); } LL LCM(LL x,LL y){ return x/GCD(x,y)*y; } const double EPS = 1E-10; const int MOD = 998244353; const int N = 200000+5; const int dx[] = {-1,1,0,0,1,-1,1,1}; const int dy[] = {0,0,-1,1,-1,1,-1,1}; using namespace std;struct Edge{LL from,to;LL cap,flow;Edge(){}Edge(LL from,LL to,LL cap,LL flow):from(from),to(to),cap(cap),flow(flow){} }; LL n,m; //結點數,邊數(含反向弧) LL S,T; //源點、匯點 vector<Edge> edges; //邊表,edges[e]和edges[e^1]互為反向弧 vector<LL> G[N]; //鄰接表,G[i][j]表示結點i的第j條邊在e數組中的序號 bool vis[N]; //BFS使用,標記一個節點是否被遍歷過 LL dis[N]; //dis[i]表從起點s到i點的距離(層次) LL cur[N]; //cur[i]表當前正訪問i節點的第cur[i]條弧 set<LL> cutSet; //最小割 bool flag; //是否求最小割 void addEdge(LL from,LL to,LL cap){edges.push_back( Edge(from,to,cap,0) );edges.push_back( Edge(to,from,0,0) );LL m=edges.size();G[from].push_back(m-2);G[to].push_back(m-1); } bool BFS(){//構建層次網絡memset(vis,0,sizeof(vis));dis[S]=0;vis[S]=true;//將超級源點加入最小割// if(flag)// cutSet.insert(S);queue<LL> Q;//用來保存節點編號Q.push(S);while(!Q.empty()){LL x=Q.front();Q.pop();for(LL y=0;y<G[x].size();y++){Edge& e=edges[G[x][y]];if(!vis[e.to] && e.cap>e.flow){vis[e.to]=true;dis[e.to]=dis[x]+1;Q.push(e.to);if(flag)//記錄最小割元素cutSet.insert(e.to);}}}return vis[T]; }LL DFS(LL x,LL cp){//cp表示從s到x目前為止所有弧的最小殘量if(x==T || cp==0)return cp;LL flow=0,newFlow;//flow用來記錄從x到t的最小殘量for(LL &y=cur[x];y<G[x].size();y++){Edge &e=edges[G[x][y]];if(dis[x]+1==dis[e.to]){LL minn=min(cp,e.cap-e.flow);newFlow=DFS(e.to,minn);if(newFlow>0){e.flow+=newFlow;edges[G[x][y]^1].flow-=newFlow;flow+=newFlow;cp-=newFlow;if(cp==0)break;}}}return flow; } LL Dinic(){LL flow=0;while(BFS()){memset(cur,0,sizeof(cur));flow+=DFS(S,INF);}return flow; } int main(){scanf("%lld%lld",&n,&m);S=0,T=n+1;//超級源、匯LL sum=0;//正權值之和for(LL i=1;i<=n;i++){LL x;scanf("%lld",&x);if(x>0){addEdge(S,i,x);sum+=x;}elseaddEdge(i,T,-x);}for(LL i=1;i<=m;i++){LL x,y;scanf("%lld%lld",&x,&y);addEdge(x,y,INF);}flag=false;//不統計最小割所屬元素LL minCut=Dinic();//計算最小割的值flag=true;//統計最小割所屬元素BFS();//構建層次網絡printf("%d ",cutSet.size());//最小割個數printf("%lld\n",sum-minCut);//最大權閉合子圖的權值return 0; }

?

總結

以上是生活随笔為你收集整理的Firing（POJ-2987）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。