http://poj.org/problem?id=2987
题意：
公司要由于经济 问题 要 裁员工，已知，要采取某个 员工，那么 他的下属也将被 裁去，给出 裁出 n 个员公的 所获的利益 （可负 可正） ，员工之间的关系 i j，
i 以 j 做为 他的下属 求在获得 最大利益的情况下 ，最少 裁 多少人 。
输出 裁的人数 和 利益 。
题接： 因为 员工 i 以 其上司的 存在 而 存在， 所以 他们 之间 有 依赖关系 ， 可应用 最大权闭合图，求解 。
View Code 
1 #include<cstdio>
2 #include<cstring>
3 #include<cmath>
4 #include<iostream>
5 #include<algorithm>
6 #include<set>
7 #include<map>
8 #include<queue>
9 #include<vector>
10 #include<string>
11 #define Min(a,b) a<b?a:b
12 #define Max(a,b) a>b?a:b
13 #define CL(a,num) memset(a,num,sizeof(a));
14 #define maxn 5100
15 #define eps 1e-6
16 #define inf 10000000000
17 #define read() freopen("data.in","r",stdin) ;
18 #define ll __int64
19 using namespace std;
20 ll n , m ;
21 struct node
22 {
23 int from;
24 int to ;
25 ll flow ;
26 int next ;
27 } p[maxn*20];
28 int head[maxn] ,s,t,cnt,dis[maxn];
29 ll a[maxn] ,ans,num,sum;
30
31 bool vis[maxn] ;
32
33 queue<int>que ;
34 void add(int from ,int to , ll flow )
35 {
36 p[cnt].to = to ;
37 p[cnt].flow =flow ;
38 p[cnt].next = head[from] ;
39 head[from] = cnt++ ;
40
41 p[cnt].to = from ;
42 p[cnt].flow = 0 ;
43 p[cnt].next = head[to] ;
44 head[to] = cnt++ ;
45
46 }
47
48 int bfs()
49 {
50 CL(dis,-1) ;
51 dis[s] = 0 ;
52 int i ;
53 while(!que.empty())que.pop() ;
54
55 que.push(s) ;
56 while(!que.empty())
57 {
58 int u = que.front() ;que.pop() ;
59
60 for(i = head[u] ; i != -1 ;i = p[i].next)
61 {
62 int v = p[i].to ;
63
64 ll flow = p[i].flow ;
65
66 if(flow > 0)
67 if(dis[v] < 0 )
68 {
69 dis[v] = dis[u] + 1 ;
70 que.push(v) ;
71 }
72
73 }
74
75 }
76
77 if(dis[t] > 0) return 1;
78 else return 0 ;
79
80
81
82 }
83
84
85 ll dfs(int x,ll mx)
86 {
87
88
89 if(x == t) return mx ;
90
91 int i ;
92 ll a ,tf = 0;
93
94
95 for(i = head[x] ; i != -1 ; i = p[i].next)
96 {
97 int v = p[i].to ;
98 ll flow = p[i].flow ;
99 if(flow > 0)
100 {
101 if( dis[v] == dis[x] + 1 && (a = dfs(v,min(flow ,mx))))
102 {
103 p[i].flow -= a ;
104 p[i^1].flow += a;
105
106 return a ;
107 }
108
109 }
110
111 }
112
113
114 if(!tf) dis[x] = - 1;
115 return tf ;
116
117 }
118 void dfs1(int x)
119 {
120
121
122 vis[x] = true ;
123 num++;
124
125 for(int i = head[x] ;i != -1;i = p[i].next)
126 {
127 int v = p[i].to ;
128 if(!vis[v] && p[i].flow > 0)
129 dfs1(v) ;
130 }
131 }
132 void dinic()
133 {
134
135 ans = 0 ;
136 ll res = 0 ;
137 while(bfs())
138 {
139 while(res = dfs(s,inf))ans += res ;
140 }
141
142 CL(vis,false) ;
143
144 num = 0 ;
145 dfs1(s) ;
146
147 printf("%I64d %I64d\n",num - 1,sum - ans) ;
148
149
150 }
151 int main()
152 {
153 int i,x,y ;
154
155 //read() ;
156 while(scanf("%I64d%I64d",&n,&m)!=EOF)
157 {
158 CL(head,-1) ;
159 cnt = 0 ;
160 sum = 0 ;
161 for(i = 1 ; i <= n;i++)
162 {
163 scanf("%I64d",&a[i]) ;
164 if(a[i] > 0)sum += a[i] ;
165 }
166
167 for(i = 0 ; i < m;i++)
168 {
169 scanf("%d%d",&x,&y);
170 add(x,y,inf) ;
171 }
172 s = 0 ;
173 t = n + 1 ;
174 for(i = 1 ;i <= n;i++)
175 {
176 if(a[i] >0)
177 {
178 add(s,i,a[i]);
179 }
180 else
181 {
182 add(i,t,-a[i]) ;
183 }
184 }
185
186 dinic() ;
187
188 }
189 }
2 #include<cstring>
3 #include<cmath>
4 #include<iostream>
5 #include<algorithm>
6 #include<set>
7 #include<map>
8 #include<queue>
9 #include<vector>
10 #include<string>
11 #define Min(a,b) a<b?a:b
12 #define Max(a,b) a>b?a:b
13 #define CL(a,num) memset(a,num,sizeof(a));
14 #define maxn 5100
15 #define eps 1e-6
16 #define inf 10000000000
17 #define read() freopen("data.in","r",stdin) ;
18 #define ll __int64
19 using namespace std;
20 ll n , m ;
21 struct node
22 {
23 int from;
24 int to ;
25 ll flow ;
26 int next ;
27 } p[maxn*20];
28 int head[maxn] ,s,t,cnt,dis[maxn];
29 ll a[maxn] ,ans,num,sum;
30
31 bool vis[maxn] ;
32
33 queue<int>que ;
34 void add(int from ,int to , ll flow )
35 {
36 p[cnt].to = to ;
37 p[cnt].flow =flow ;
38 p[cnt].next = head[from] ;
39 head[from] = cnt++ ;
40
41 p[cnt].to = from ;
42 p[cnt].flow = 0 ;
43 p[cnt].next = head[to] ;
44 head[to] = cnt++ ;
45
46 }
47
48 int bfs()
49 {
50 CL(dis,-1) ;
51 dis[s] = 0 ;
52 int i ;
53 while(!que.empty())que.pop() ;
54
55 que.push(s) ;
56 while(!que.empty())
57 {
58 int u = que.front() ;que.pop() ;
59
60 for(i = head[u] ; i != -1 ;i = p[i].next)
61 {
62 int v = p[i].to ;
63
64 ll flow = p[i].flow ;
65
66 if(flow > 0)
67 if(dis[v] < 0 )
68 {
69 dis[v] = dis[u] + 1 ;
70 que.push(v) ;
71 }
72
73 }
74
75 }
76
77 if(dis[t] > 0) return 1;
78 else return 0 ;
79
80
81
82 }
83
84
85 ll dfs(int x,ll mx)
86 {
87
88
89 if(x == t) return mx ;
90
91 int i ;
92 ll a ,tf = 0;
93
94
95 for(i = head[x] ; i != -1 ; i = p[i].next)
96 {
97 int v = p[i].to ;
98 ll flow = p[i].flow ;
99 if(flow > 0)
100 {
101 if( dis[v] == dis[x] + 1 && (a = dfs(v,min(flow ,mx))))
102 {
103 p[i].flow -= a ;
104 p[i^1].flow += a;
105
106 return a ;
107 }
108
109 }
110
111 }
112
113
114 if(!tf) dis[x] = - 1;
115 return tf ;
116
117 }
118 void dfs1(int x)
119 {
120
121
122 vis[x] = true ;
123 num++;
124
125 for(int i = head[x] ;i != -1;i = p[i].next)
126 {
127 int v = p[i].to ;
128 if(!vis[v] && p[i].flow > 0)
129 dfs1(v) ;
130 }
131 }
132 void dinic()
133 {
134
135 ans = 0 ;
136 ll res = 0 ;
137 while(bfs())
138 {
139 while(res = dfs(s,inf))ans += res ;
140 }
141
142 CL(vis,false) ;
143
144 num = 0 ;
145 dfs1(s) ;
146
147 printf("%I64d %I64d\n",num - 1,sum - ans) ;
148
149
150 }
151 int main()
152 {
153 int i,x,y ;
154
155 //read() ;
156 while(scanf("%I64d%I64d",&n,&m)!=EOF)
157 {
158 CL(head,-1) ;
159 cnt = 0 ;
160 sum = 0 ;
161 for(i = 1 ; i <= n;i++)
162 {
163 scanf("%I64d",&a[i]) ;
164 if(a[i] > 0)sum += a[i] ;
165 }
166
167 for(i = 0 ; i < m;i++)
168 {
169 scanf("%d%d",&x,&y);
170 add(x,y,inf) ;
171 }
172 s = 0 ;
173 t = n + 1 ;
174 for(i = 1 ;i <= n;i++)
175 {
176 if(a[i] >0)
177 {
178 add(s,i,a[i]);
179 }
180 else
181 {
182 add(i,t,-a[i]) ;
183 }
184 }
185
186 dinic() ;
187
188 }
189 }