【BZOJ】【1565】【NOI2009】PVZ 植物大战僵尸

网络流/最大权闭合子图+拓扑排序

　　感动死了>_<，一年多以前刚知道网络流的时候听说了这道名字很带感的题目，现在终于有实力切掉它了。

　　这题是最大权闭合子图模型的经典应用<_<，首先我们看到有正权有负权，有些点之间还有依赖关系（保护/左右顺序）

　　对于每个点，我们向它直接保护的点连边（它左边的第一个点也视为被它保护），表示必须先吃掉这棵植物才能吃后面的，然后进行拓扑排序，对于满足拓扑关系的x->y我们建弧y->x，容量为INF，表示如果要选y就必须选x，同时对所有拓扑排序能排到的点（不在环里的点）向S/T建弧（按权值正负）。然后跑最大流即可。

  1 /**************************************************************
  2     Problem: 1565
  3     User: Tunix
  4     Language: C++
  5     Result: Accepted
  6     Time:2016 ms
  7     Memory:8000 kb
  8 ****************************************************************/
  9  
 10 //BZOJ 1565
 11 #include<vector>
 12 #include<cstdio>
 13 #include<cstring>
 14 #include<cstdlib>
 15 #include<iostream>
 16 #include<algorithm>
 17 #define rep(i,n) for(int i=0;i<n;++i)
 18 #define F(i,j,n) for(int i=j;i<=n;++i)
 19 #define D(i,j,n) for(int i=j;i>=n;--i)
 20 #define pb push_back
 21 using namespace std;
 22 inline int getint(){
 23     int v=0,sign=1; char ch=getchar();
 24     while(ch<'0'||ch>'9'){ if (ch=='-') sign=-1; ch=getchar();}
 25     while(ch>='0'&&ch<='9'){ v=v*10+ch-'0'; ch=getchar();}
 26     return v*sign;
 27 }
 28 const int N=2010,M=500000,INF=~0u>>2;
 29 typedef long long LL;
 30 /******************tamplate*********************/
 31 int n,m,tot,ans,Sum,in[N],a[N];
 32 inline int pack(int i,int j){
 33     return (i-1)*m+j;
 34 }
 35 struct edge{int to,v;};
 36 struct Net{
 37     edge E[M];
 38     int head[N],next[M],cnt;
 39     void ins(int x,int y,int v){
 40         E[++cnt]=(edge){y,v};
 41         next[cnt]=head[x]; head[x]=cnt;
 42     }
 43     void add(int x,int y,int v){
 44         ins(x,y,v); ins(y,x,0);
 45     }
 46     vector<int>G[N];
 47     int S,T,cur[N],d[N],Q[N];
 48     bool mklevel(){
 49         F(i,S,T) d[i]=-1;
 50         d[S]=0;
 51         int l=0,r=-1;
 52         Q[++r]=S;
 53         while(l<=r){
 54             int x=Q[l++];
 55             for(int i=head[x];i;i=next[i])
 56                 if (d[E[i].to]==-1 && E[i].v){
 57                     d[E[i].to]=d[x]+1;
 58                     Q[++r]=E[i].to;
 59                 }
 60         }
 61         return d[T]!=-1;
 62     }
 63     int dfs(int x,int a){
 64         if (x==T) return a;
 65         int flow=0;
 66         for(int &i=cur[x];i && flow<a;i=next[i])
 67             if (E[i].v && d[E[i].to]==d[x]+1){
 68                 int f=dfs(E[i].to,min(a-flow,E[i].v));
 69                 E[i].v-=f;
 70                 E[i^1].v+=f;
 71                 flow+=f;
 72             }
 73         if (!flow) d[x]=-1;
 74         return flow;
 75     }
 76     void Dinic(){
 77         while(mklevel()){
 78             F(i,S,T) cur[i]=head[i];
 79             ans+=dfs(S,INF);
 80         }
 81     }
 82     void top_sort(){
 83         int l=0,r=-1;
 84         F(i,1,tot) if(in[i]==0){
 85             Q[++r]=i;
 86             if (a[i]>0) {add(S,i,a[i]); Sum+=a[i];}
 87             else add(i,T,-a[i]);
 88         }
 89         while(l<=r){
 90             int x=Q[l++];
 91             rep(i,G[x].size()){
 92                 int y=G[x][i];
 93                 add(y,x,INF);
 94                 in[y]--;
 95                 if (in[y]==0){
 96                     if (a[y]>0){ add(S,y,a[y]); Sum+=a[y];}
 97                     else add(y,T,-a[y]);
 98                     Q[++r]=y;
 99                 }
100             }
101         }
102     }
103     void init(){
104         n=getint(); m=getint(); cnt=1;
105         tot=n*m; S=0; T=tot+1; Sum=ans=0;
106         int x,y,p;
107         F(i,1,n) F(j,1,m){
108             a[pack(i,j)]=getint();
109             p=getint();
110             F(k,1,p){
111                 x=getint()+1; y=getint()+1;
112                 G[pack(i,j)].pb(pack(x,y));
113                 in[pack(x,y)]++;
114             }
115             if (j>1){
116                 G[pack(i,j)].pb(pack(i,j-1));
117                 in[pack(i,j-1)]++;
118             }
119         }
120         top_sort();
121         Dinic();
122         printf("%d
",Sum-ans);
123     }
124 }G1;
125  
126 int main(){
127 #ifndef ONLINE_JUDGE
128     freopen("1565.in","r",stdin);
129     freopen("1565.out","w",stdout);
130 #endif
131     G1.init();
132     return 0;
133 }

View Code

1565: [NOI2009]植物大战僵尸

Time Limit: 10 Sec Memory Limit: 64 MB
Submit: 1619 Solved: 756
[Submit][Status][Discuss]

Description

Input

Output

仅包含一个整数，表示可以获得的最大能源收入。注意，你也可以选择不进行任何攻击，这样能源收入为0。

Sample Input

3 2
10 0
20 0
-10 0
-5 1 0 0
100 1 2 1
100 0

Sample Output

HINT

在样例中, 植物P1,1可以攻击位置(0,0), P2, 0可以攻击位置(2,1)。
一个方案为，首先进攻P1,1, P0,1，此时可以攻击P0,0 。共得到能源收益为(-5)+20+10 = 25。注意, 位置(2,1)被植物P2,0保护，所以无法攻击第2行中的任何植物。
【大致数据规模】
约20%的数据满足1 ≤ N, M ≤ 5；
约40%的数据满足1 ≤ N, M ≤ 10；
约100%的数据满足1 ≤ N ≤ 20，1 ≤ M ≤ 30，-10000 ≤ Score ≤ 10000 。

Source

[Submit][Status][Discuss]