[NOI2009][BZOJ1565] 植物大战僵尸

1565: [NOI2009]植物大战僵尸

Time Limit: 10 Sec Memory Limit: 64 MB
Submit: 1654 Solved: 769
[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

首先拓扑排序找环，从环上的每个点开始dfs找出所有保护的点，把这些点全都去掉。最后重建图，就是最大权闭合图，跑最大流就好了。

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstdlib>
  4 #include<cstring>
  5 #include<algorithm>
  6 #include<cmath>
  7 #include<vector>
  8 #include<set>
  9 #include<queue>
 10 #define INF 100000007
 11 using namespace std;
 12 int sumx,ans,edge,n,m,sum,x,y,num,tot;
 13 int w[666],dis[666],q[666],head[666],head0[666],list[500000],list0[500000],next[500000],next0[500000],key[500000];
 14 int ind[666],topo[666];
 15 bool v[666];
 16 void insert(int x,int y)
 17 {
 18     next[++edge]=head[x];
 19     head[x]=edge;
 20     list[edge]=y;
 21 }
 22 void insert0(int x,int y,int z)
 23 {
 24     next0[++edge]=head0[x];
 25     head0[x]=edge;
 26     list0[edge]=y;
 27     key[edge]=z;
 28 }
 29 int find()
 30 {
 31     for (int i=1;i<=n*m;i++) if (!ind[i]) return i;
 32     return -1;
 33 }
 34 void toposort()
 35 {
 36     for (int i=1;i<=n*m;i++)
 37     {
 38         int k=find();
 39         if (k==-1) break;
 40         topo[++tot]=k;
 41         ind[k]=-1;
 42         for (int j=head[k];j;j=next[j]) ind[list[j]]--;
 43     }
 44 }
 45 void dfs(int x)
 46 {
 47     for (int i=head[x];i;i=next[i]) 
 48         if (v[list[i]])
 49         {
 50             v[list[i]]=0;
 51             dfs(list[i]);
 52         }
 53 }
 54 void rebuild()
 55 {
 56     edge=1;
 57     for (int i=1;i<=n*m;i++) 
 58     {
 59         if (!v[i]) continue;
 60         if (w[i]>0)
 61         {
 62             insert0(0,i,w[i]);
 63             insert0(i,0,0);
 64         }
 65         if (w[i]<0)
 66         {
 67             insert0(i,n*m+1,-w[i]);
 68             insert0(n*m+1,i,0);
 69         }
 70         for (int j=head[i];j;j=next[j])
 71             if (v[list[j]]) 
 72             {
 73                 insert0(list[j],i,INF);
 74                 insert0(i,list[j],0);
 75             }
 76     }
 77 }
 78 bool BFS()
 79 {
 80     memset(dis,0xff,sizeof(dis));
 81     int x,t=0,w=1;
 82     q[1]=0; dis[0]=1;
 83     while (t<w)
 84     {
 85         x=q[++t];
 86         for (int i=head0[x];i;i=next0[i])
 87             if (key[i]&&dis[list0[i]]==-1)
 88             {
 89                 dis[list0[i]]=dis[x]+1;
 90                 q[++w]=list0[i];
 91             }
 92     }
 93     return dis[n*m+1]!=-1;
 94 }
 95 int find(int x,int flow)
 96 {
 97     if (x==n*m+1) return flow;
 98     int used=0,a;
 99     for (int i=head0[x];i;i=next0[i])
100         if (key[i]&&dis[list0[i]]==dis[x]+1)
101         {
102                                         a=flow-used;
103                                         a=find(list0[i],min(key[i],a));
104                                         key[i]-=a;
105                                         key[i^1]+=a;
106                                         used+=a;
107                                         if (used==flow) return flow;
108         }
109     if (!used) dis[x]=-1;
110     return used;
111 }
112 int main()
113 {
114     memset(v,0,sizeof(v));
115     scanf("%d%d",&n,&m);
116     for (int i=1;i<=n*m;i++)
117     {
118         scanf("%d%d",&w[i],&sum);
119         for (int j=1;j<=sum;j++)
120         {
121             scanf("%d%d",&x,&y);
122             num=x*m+y+1;
123             insert(i,num);
124             ind[num]++;
125         }
126     }
127     for (int i=0;i<n;i++)
128         for (int j=0;j<m-1;j++)
129         {
130             num=i*m+j+1;
131             insert(num+1,num);
132             ind[num]++;
133         }
134     toposort();
135     for (int i=1;i<=tot;i++) v[topo[i]]=1;
136     for (int i=1;i<=n*m;i++) 
137         if (!v[i]) dfs(i);
138     for (int i=1;i<=n*m;i++) 
139         if (w[i]>0&&v[i]) sumx+=w[i];
140     rebuild();
141     ans=0;
142     while (BFS()) ans+=find(0,INF); 
143     printf("%d",sumx-ans);
144     return 0;
145 }