hdu 3061：Battle（最大权闭合图）

http://acm.hdu.edu.cn/showproblem.php?pid=3061

Problem Description

由于小白同学近期习武十分刻苦，很快被晋升为天策军的统帅。而他上任的第一天，就面对了一场极其困难的战斗： 据侦查兵回报，前方共有N座城池，考虑到地势原因，最终得到一个结论：攻占某些城池之前必须攻占另外一些城池。 事实上，可以把地图看做是一张拓扑图，而攻占某个城池，就意味着必须先攻占它的所有前驱结点。 小白还做了一份调查，得到了攻占每个城池会对他的兵力产生多少消耗（当然也可能会得到增长，因为每攻占一个城池，便可以整顿军队，扩充兵力，天策军的兵力十分庞大，如果不考虑收益，他们可以攻取所有的城池）。 现在请你帮小白统帅做一份战斗计划，挑选攻打哪些城市，使得天策军在战斗过后军容最为壮大。

 

 

Input

首先输入一个N 代表有N个城池（1<= n <= 500） 接着输入一个M，代表城池和城池之间的拓扑关系数。 接着输入N个数字 代表从1 到 N 编号城池的战斗消耗（负数代表将要消耗天策军兵力，正数表示天策军可以获得相应的战斗收益） 最后M行 每行2个数字 a，b，代表相应城池的编号。 表示攻占b之后才可以攻占a；

 

 

Output

天策军最大能获得多少战斗收益

 

 

Sample Input

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

 

 

Sample Output

2

解题思路：

把所有权值为正的点与源点相连，权值为点的权值，

把所有权值为负的点与汇点相连，权值为点权值的绝对值，

b为a的前驱，建一条a到b的边，权值为无穷。

求最大流，答案为所有正权值之后减最大流。

Dinic算法可过：

#include <stdio.h> #include <string.h> #include <algorithm> #include <vector> #include <queue> #include <math.h> #define N 550 using namespace std; int n, m, dis[N], iter[N], inf=0x9f9f9f; struct edge{ int v; int w; int rev; }; vector<edge>e[N]; void add(int u, int v, int w) { e[u].push_back(edge{v, w, e[v].size()}); e[v].push_back(edge{u, 0, e[u].size() - 1 }); } void bfs(int s) { int u, v; queue<int>q; memset(dis, -1, sizeof(dis)); dis[s]=0; q.push(s); while(!q.empty()) { u=q.front(); q.pop(); for(v = 0; v < e[u].size(); v++) { edge G=e[u][v]; if(G.w > 0 && dis[G.v] < 0) { q.push(G.v); dis[G.v] = dis[u] + 1; } } } } int dfs(int s, int t, int f) { int v, d; if (s == t) return f; for (int &i = iter[s]; i < e[s].size(); i++) { edge &G = e[s][i]; if (G.w > 0 && dis[s] < dis[G.v]) { d = dfs(G.v, t, min(f, G.w)); if (d > 0) { G.w -= d; e[G.v][G.rev].w += d; return d; } } } return 0; } int Dinic(int s, int t) { int d, sum = 0; while(1) { bfs(s); if(dis[t] < 0) return sum; memset(iter, 0, sizeof(iter)); while((d=dfs(s, t, inf)) > 0) sum+=d; } return sum; } int main() { int i, u, v, w, sum; while (scanf("%d%d", &n, &m) != EOF) { for(i=0; i<=n+1; i++) e[i].clear(); sum = 0; for (i = 1; i <= n; i++) { scanf("%d", &w); if (w > 0) { sum += w; add(0, i, w); } else add(i, n + 1, abs(w)); } for (i = 1; i <= m; i++) { scanf("%d%d", &u, &v); add(u, v, inf); } printf("%d\n", sum - Dinic(0, n+1)); } return 0; }

EK算法，TLE。

#include <stdio.h> #include <string.h> #include <algorithm> #include <queue> #include <math.h> #define N 550 using namespace std; int n, m, inf=0x9f9f9f; int e[N][N], flow[N], pre[N]; queue<int>q; int bfs(int s, int t) { while (!q.empty()) q.pop(); int u, v; flow[s] = inf; q.push(s); while (!q.empty()) { u = q.front(); q.pop(); if (u == t) break; for (v = 0; v <= n + 1; v++) { if (e[u][v] && v != s && pre[v]==-1) { q.push(v); flow[v] = min(flow[u], e[u][v]); pre[v] = u; } } } if (pre[t] == -1) return - 1; return flow[t]; } int EK(int s, int t) { int d, p, sum = 0; while (1) { memset(pre, -1, sizeof(pre)); d = bfs(s, t); if (d == -1) break; sum += d; p = t; while (p != s) { e[pre[p]][p] -= d; e[p][pre[p]] += d; p = pre[p]; } } return sum; } int main() { int i, u, v, w, sum=0; while (scanf("%d%d", &n, &m) != EOF) { memset(e, 0, sizeof(e)); for (i = 1; i <= n; i++) { scanf("%d", &w); if (w > 0) { sum += w; e[0][i] = w; } else e[i][n + 1] = abs(w); } for (i = 1; i <= m; i++) { scanf("%d%d", &u, &v); e[u][v] = inf; } printf("%d\n", sum - EK(0, n+1)); } return 0; }

FF算法， 也是TLE：

#include <stdio.h> #include <string.h> #include <algorithm> #include <vector> #include <queue> #include <math.h> #define N 550 using namespace std; int n, m, book[N], inf=0x9f9f9f; struct edge{ int v; int w; int rev; }; vector<edge>e[N]; void add(int u, int v, int w) { e[u].push_back(edge{v, w, e[v].size()}); e[v].push_back(edge{u, 0, e[u].size() - 1 }); } int dfs(int s, int t, int f) { book[s] = 1; int v, d; if (s == t) return f; for (v = 0; v < e[s].size(); v++) { edge & G = e[s][v]; if (G.w && book[G.v]==0) { d = dfs(G.v, t, min(f, G.w)); if (d > 0) { G.w -= d; e[G.v][G.rev].w += d; return d; } } } return 0; } int FF(int s, int t) { int d, sum = 0; while (1) { memset(book, 0, sizeof(book)); d = dfs(s, t, inf); if (d == 0) break; sum += d; } return sum; } int main() { int i, u, v, w, sum=0; while (scanf("%d%d", &n, &m) != EOF) { memset(e, 0, sizeof(e)); for (i = 1; i <= n; i++) { scanf("%d", &w); if (w > 0) { sum += w; add(0, i, w); } else add(i, n + 1, abs(w)); } for (i = 1; i <= m; i++) { scanf("%d%d", &u, &v); add(u, v, inf); } printf("%d\n", sum - FF(0, n+1)); } return 0; }