HDU

题意：

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

思路：

一开始一直没有想出来，后来看了蒟巨的网络流建图博客才发现，这就是一个裸的最大权闭合子图问题（还是太菜了呀-very vegetable）；

顺便再补充一下最大权闭合子图的概念：

参考：胡伯涛《最小割模型在信息学竞赛中的应用》

定义：

有向图的闭合图：闭合图内任一点的任意后继结点也一定还在闭合图中。

物理意义：事物间的依赖关系，一件事情要发生，它需要的所有前提条件也都一定要发生。

最大权闭合图：点权之和最大的闭合图。

建图：

设置超级源汇S，T。

然后使$S$和所有的正权的点连接权值为点权的边，所有点权为负的点和$T$连接权值为点权绝对值的边。然后如果选择了某个$v$点才可以选$u$点，那么把u向v连接一条权值为$infty$ $\infty$

最大点权和=正点权和-最小割。证明略

  1 /*
  2 *  Author: windystreet
  3 *  Date  : 2018-08-20 09:25:36
  4 *  Motto : Think twice, code once.
  5 */
  6 #include<bits/stdc++.h>
  7 
  8 using namespace std;
  9 
 10 #define X first
 11 #define Y second
 12 #define eps  1e-5
 13 #define gcd __gcd
 14 #define pb push_back
 15 #define PI acos(-1.0)
 16 #define lowbit(x) (x)&(-x)
 17 #define bug printf("!!!!!
");
 18 #define mem(x,y) memset(x,y,sizeof(x))
 19 
 20 typedef long long LL;
 21 typedef long double LD;
 22 typedef pair<int,int> pii;
 23 typedef unsigned long long uLL;
 24 
 25 const int maxn = 505;
 26 const int INF  = 1<<30;
 27 const int mod  = 1e9+7;
 28 
 29 struct Edge{
 30      int from,to,cap,flow;
 31 };
 32 
 33 struct Dinic
 34 {
 35     int n,m,s,t;
 36     vector<Edge>edge;
 37     vector<int>G[maxn];
 38     bool vis[maxn];
 39     int d[maxn];
 40     int cur[maxn];
 41     void init(int n){
 42         this->n = n;
 43         for(int i=0;i<=n;i++)G[i].clear(),edge.clear();
 44     }
 45     inline void addedge(int from,int to,int cap){
 46         edge.pb((Edge){from,to,cap,0});
 47         edge.pb((Edge){to,from,0,0});
 48         m = edge.size();
 49         G[from].pb(m-2);
 50         G[to].pb(m-1);
 51     }
 52     inline bool bfs(){
 53         mem(vis,0);
 54         queue<int>Q;
 55         Q.push(s);
 56         d[s] = 0;
 57         vis[s] = 1;
 58         while(!Q.empty()){
 59             int x = Q.front(); Q.pop();
 60             int sz = G[x].size();
 61             for(int i=0;i<sz;++i){
 62                 Edge &e = edge[G[x][i]];
 63                 if(!vis[e.to] && e.cap>e.flow){
 64                     vis[e.to] = 1 ;
 65                     d[e.to] = d[x] + 1;
 66                     Q.push(e.to); 
 67                 }
 68             }
 69         }
 70         return vis[t];
 71     }
 72     inline int dfs(int x,int a){
 73         if(x == t || a == 0)return a;
 74         int flow = 0,f;
 75         int sz = G[x].size();
 76         for(int &i = cur[x];i<sz;i++){
 77             Edge &e = edge[G[x][i]];
 78             if(d[x] + 1 == d[e.to] && (f = dfs(e.to,min(a,e.cap - e.flow)))>0){
 79                 e.flow += f;
 80                 edge[G[x][i]^1].flow -=f;
 81                 flow += f;
 82                 a -= f;
 83                 if(a==0)break;
 84             }
 85         }
 86         if(!flow) d[x] = -2;  //炸点优化
 87         return flow;
 88     }
 89     inline int maxflow(int s,int t){
 90         this->s = s; this -> t = t;
 91         int flow = 0;
 92         while(bfs()){
 93             mem(cur,0);
 94             flow += dfs(s,INF);
 95         }
 96         return flow;
 97     }
 98 };
 99 
100 int s[maxn];
101 void solve(){
102     int n,m,sum,x,y;
103     while(scanf("%d%d",&n,&m)!=EOF){
104         Dinic dinic;
105         sum = 0;
106         int S = 0,T = n+2;
107         for(int i=1;i<=n;i++){
108             scanf("%d",s+i);
109             if(s[i]>0){
110                 sum+=s[i];
111                 dinic.addedge(S,i,s[i]);        // 权值为正的点与源点S相连
112             }else{
113                 dinic.addedge(i,T,-s[i]);       // 否则与汇点T相连
114             }
115         }
116         for(int i=1;i<=m;i++){
117             scanf("%d%d",&x,&y);
118             dinic.addedge(x,y,INF);             // 在y的前提下发生x，则加入边x->y，权值为inf
119         }
120         printf("%d
",sum-dinic.maxflow(S,T));
121     }
122 
123     return;
124 }
125 
126 int main()
127 {
128 //    freopen("F:\in.txt","r",stdin);
129 //    freopen("out.txt","w",stdout);
130 //    ios::sync_with_stdio(false);
131     int t = 1;
132     //scanf("%d",&t);
133     while(t--){
134     //    printf("Case %d: ",cas++);
135         solve();
136     }
137     return 0;
138 }