題目連結：http://poj.org/problem?id=2987
題目大意：一個公司有n個員工（裡面包括董事長，經理，普通員工等等），現在遇見了金融危機，公司要開始裁員了，每個人對公司的價值不一樣（可能為正可能為負），當你裁員一個員工時，這個員工他手下的員工必須一起裁掉，問你如何裁員能使公司得到的利益最大，而這種裁員方法必須得裁掉多少個員工。
建圖模型：最大權閉合子圖指選擇u，則u以下關系的都要選，一定要選到底，不能跳過u選它以下的。增設一個超級源點和一個超級彙點，（1->n）的點中，當點權為正時，從源點向該點連一條權值為點權大小的邊，當點權為負時，從該點連一條權值大小為它的絕對值的邊連向彙點。這種問題一般都是對于（u，v），如果選擇u必須選擇v，對（u，v）連一條容量為oo的邊。
裁員數等于靠近源點最小割一邊的點數，最大利益=所有點正權值之和-最小割。
View Code
1 #include <iostream>
2 #include <cstdio>
3 #include <cstring>
4 #include <queue>
5 #include <algorithm>
6 using namespace std;
7
8 const int mn=5555;
9 const int mm=222222;
10 const int oo=1e9;
11 int node, st, sd, edge;
12 int ver[mm], flow[mm], next[mm];
13 int head[mn], work[mn], dis[mn], q[mn], visit[mn];
14
15 inline void init(int _node, int _st, int _sd)
16 {
17 node=_node, st=_st, sd=_sd;
18 for(int i=0; i<node; i++)
19 head[i]=-1;
20 edge=0;
21 }
22
23 void addedge(int u, int v, int c1, int c2)
24 {
25 ver[edge]=v, flow[edge]=c1, next[edge]=head[u],head[u]=edge++;
26 ver[edge]=u, flow[edge]=c2, next[edge]=head[v],head[v]=edge++;
27 }
28 bool Dinic_bfs()
29 {
30 int i,u,v,l,r=0;
31 for(i=0; i<node; ++i)dis[i]=-1;
32 dis[q[r++]=st]=0;
33 for(l=0; l<r; ++l)
34 for(i=head[u=q[l]]; i>=0; i=next[i])
35 if(flow[i]&&dis[v=ver[i]]<0)
36 {
37 dis[q[r++]=v]=dis[u]+1;
38 if(v==sd)return 1;
39 }
40 return 0;
41 }
42 long long Dinic_dfs(int u, int exp)
43 {
44 if(u==sd) return exp;
45 for(int &i=work[u]; i>=0; i=next[i])
46 {
47 int v=ver[i], tp;
48 if(flow[i]&&dis[v]==dis[u]+1&&(tp=Dinic_dfs(v,min(flow[i],exp)))>0)
49 {
50 flow[i]-=tp;
51 flow[i^1]+=tp;
52 return tp;
53 }
54 }
55 return 0;
56 }
57 long long Dinic_flow()
58 {
59 int i,delta;
60 long long ret=0;
61 while(Dinic_bfs())
62 {
63 for(i=0; i<node; ++i)work[i]=head[i];
64 while(delta=Dinic_dfs(st,oo))ret+=delta;
65 }
66 return ret;
67 }
68
69 void DFS(int u)
70 {
71 visit[u]=1;
72 for(int i=head[u], v; i>=0; i=next[i])
73 if(flow[i]>0&&!visit[v=ver[i]]) DFS(v);
74 }
75
76 int main()
77 {
78 int n, m, w, u, v;
79 while(~scanf("%d%d",&n,&m))
80 {
81 init(n+2,0,n+1);
82 long long sum=0;
83 for(int i=1; i<=n; i++)
84 {
85 scanf("%d",&w);
86 if(w>0) sum+=w,addedge(st,i,w,0);
87 if(w<0) addedge(i,sd,-w,0);;
88 }
89 while(m--)
90 {
91 scanf("%d%d",&u,&v);
92 addedge(u,v,oo,0);
93 }
94 long long maxflow=Dinic_flow();
95 memset(visit,0,sizeof(visit));
96 DFS(st);
97 int ans=0;
98 for(int i=1; i<=n; i++) ans+=visit[i];
99 printf("%d %I64d\n",ans,sum-maxflow);
100 }
101 return 0;
102 } 轉載于:https://www.cnblogs.com/kane0526/archive/2013/04/05/3001557.html