传送门：HDU - 3061
题目描述
由于小白同学近期习武十分刻苦，很快被晋升为天策军的统帅。而他上任的第一天，就面对了一场极其困难的战斗：
据侦查兵回报，前方共有N座城池，考虑到地势原因，最终得到一个结论：攻占某些城池之前必须攻占另外一些城池。
事实上，可以把地图看做是一张拓扑图，而攻占某个城池，就意味着必须先攻占它的所有前驱结点。
小白还做了一份调查，得到了攻占每个城池会对他的兵力产生多少消耗（当然也可能会得到增长，因为每攻占一个城池，便可以整顿军队，扩充兵力，天策军的兵力十分庞大，如果不考虑收益，他们可以攻取所有的城池）。
现在请你帮小白统帅做一份战斗计划，挑选攻打哪些城市，使得天策军在战斗过后军容最为壮大。
输入描述
首先输入一个N 代表有N个城池（1<= n <= 500）
接着输入一个M，代表城池和城池之间的拓扑关系数。
接着输入N个数字 代表从1 到 N 编号城池的战斗消耗（负数代表将要消耗天策军兵力，正数表示天策军可以获得相应的战斗收益）
最后M行 每行2个数字 a，b，代表相应城池的编号。
表示攻占b之后才可以攻占a；
输出描述
天策军最大能获得多少战斗收益
思路分析
最大权闭合图模板，ans=sum-maxflow
建图方式如下：
- 建立源点s，连接源点与所有正权的点。
- 建立汇点t，连接汇点与所有负权的点，权值为绝对值。
- 讲有依赖关系的点连边，权值为INF，比如a的攻占需要先攻占b，则连a–>b的有向边，权值为INF。
最后所以正权和-最大流就是答案
样例输入
5 5
8
-8
-10
12
-10
1 2
2 5
1 4
3 4
4 5
样例输出
2
AC代码
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <cmath>
#include <vector>
#include <string>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <functional>
#if __cplusplus >= 201103L
#include <unordered_map>
#include <unordered_set>
#endif
#define ls ro<<1
#define fi first
#define se second
#define rs ro<<1|1
#define ll long long
#define pb push_back
#define vi vector<int>
#define lowbit(x) x&(-x)
#define pii pair<int,int>
#define lson ro<<1,l,mid
#define umap unordered_map
#define uset unordered_set
#define rson ro<<1|1,mid+1,r
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);
using namespace std;
const int INF = 0x3f3f3f3f;
const int N=5555,M=1000010;
struct node{
int v,w,next;
}e[M];
int head[N],h[N],cnt,n,m,s,t;
inline void adde(int u,int v,int w){
e[++cnt].v=v;
e[cnt].w=w;
e[cnt].next=head[u];
head[u]=cnt;
}
inline void add(int u,int v,int w){
adde(u,v,w);
adde(v,u,0);
}
inline bool bfs(){
queue<int>q;
mem(h,0);
h[s]=1;
q.push(s);
while(!q.empty()){
int u=q.front();
q.pop();
if(u==t)
return 1;
for(int i=head[u];i;i=e[i].next){
if(e[i].w && !h[e[i].v]){
q.push(e[i].v);
h[e[i].v]=h[u]+1;
}
}
}
return 0;
}
inline int dfs(int u,int f){
if(u==t)
return f;
int fl=0;
for(int i=head[u];i&&f;i=e[i].next){
int v=e[i].v;
if(h[v]==h[u]+1 && e[i].w){
int nx=dfs(v,min(f,e[i].w));
e[i].w-=nx;
e[i^1].w+=nx;
f-=nx;
fl+=nx;
}
}
if(!fl)
h[u]=-2;
return fl;
}
inline int dinic(){
int ans=0;
while(bfs()){
ans+=dfs(s,INF);
}
return ans;
}
int main() {
while(~scanf("%d%d",&n,&m)){
cnt=1;
mem(head,0);
t=n+1;
int sum=0;
for(int i=1;i<=n;i++){
int x;
scanf("%d",&x);
if(x>0){
add(s,i,x);
sum+=x;
}else{
add(i,t,-x);
}
}
for(int i=0;i<m;i++){
int u,v;
scanf("%d%d",&u,&v);
add(u,v,INF);
}
printf("%d\n",sum-dinic());
}
return 0;
}
