[题解]bzoj1565(NOI2009)植物大战僵尸

在样例中, 植物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 。

Solution

        这一题可以看出是最大权闭合子图。说下啥是最大权闭合 图。在一个有向图中，每个点集有一个权值。要求选择一个点集使得权值最大。选出的点满足，对于任何一条边<u,v>，若选择了u则必须选择 v。满足这个条件的顶点集叫做最大权闭合子图。在下图中，最大的权闭合子图为{3,4,5}，价值为4。

（2）如何求最大权闭合子图？构图方法：增加原点s和汇点t。原图中的权值x大于0的点，连边<s,i,x>，权值为负的点连边<i,t,-x>。原图中的边权值INF。上图改造后得到的是下面的图。设新图中与s相连的点的权值和为sum，新图的最小割即最大流为w，则答案为sum-w。下图的sum=12,w=8。

（3）最大权闭合图强调的是点之间的依赖关系，即选择某个点必须选择另外某些点。在本题中，恰有这样的性质。比如，僵尸必须从右向左，因此，选择左侧的点，就必须选择右侧的点；某个格子被另外的一些格子保护，那么要选择这个格子，必须要先选择另外的那些格子。我们正好可以用这个性质建立图进行求解。另外，在本题中有可能存在环，即比如同一行右侧的点被左侧的点保护，那么是无法吃掉这些位置的植物的。因此，首先拓扑排序一次，标记哪些格子不在环中。那么只有这些点是可以到达的。

        注意有个细节让我WA了一中午：如果某个点被一个环上的节点保护，那么他也必须标记为不可摧毁。同理要继续下去：某个节点被一个不可摧毁的节点保护，那么他也不可摧毁（而他不一定在环上）。所以我在找出环上节点之后，暴力dfs了一轮来标记所有不可摧毁的点。

代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;const int maxn=610,oo=0x7fffffff;
struct edge{int to,size,next,same;
}e[maxn*maxn];
int n,m,num=0,top=0,mark[maxn][maxn],dep[maxn],que[maxn],a[maxn];
int head[maxn],cur[maxn],ans=0;
bool exist[maxn],vis[maxn],f[maxn][maxn];void adde(int u,int v,int w){e[++num].to=v;e[num].size=w;e[num].next=head[u];head[u]=num;
}
void add(int u,int v,int w){adde(u,v,w);e[num].same=num+1;f[u][v]=true;adde(v,u,0);e[num].same=num-1;
}
void DFS(int x){for(int i=1;i<=top;i++){if(exist[i]&&f[i][x]){exist[i]=false;DFS(i);}}
}
void Init(){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){mark[i][j]=++top;}}for(int i=1;i<=n;i++){for(int j=1,k;j<=m;j++){scanf("%d%d",&a[mark[i][j]],&k);for(int l=1,u,v;l<=k;l++){scanf("%d%d",&u,&v);add(mark[++u][++v],mark[i][j],oo);}if(j>1)add(mark[i][j-1],mark[i][j],oo);}}for(int i=1;i<=top;i++)for(int j=1;j<=top;j++)for(int k=1;k<=top;k++)f[j][k]|=f[j][i]&&f[i][k];memset(exist,1,sizeof exist);for(int i=1;i<=top;i++){if(f[i][i]){exist[i]=false;DFS(i);}}for(int i=1;i<=top;i++){if(exist[i]){if(a[i]>0){ans+=a[i];add(0,i,a[i]);}else{add(i,top+1,-a[i]);}}}
}
bool bfs(){memset(dep,0,sizeof dep);memset(que,0,sizeof que);int h=0,t=1;dep[que[t]=0]=1;while(h<t){int x=que[++h];for(int i=head[x];i;i=e[i].next){if(!dep[e[i].to]&&e[i].size&&exist[e[i].to]){que[++t]=e[i].to;dep[e[i].to]=dep[x]+1;if(e[i].to==top+1)return true;}}}return false;
}
int dfs(int x,int flow){if(x==top+1||(!flow))return flow;int temp;for(int &i=cur[x];i;i=e[i].next){if(dep[e[i].to]==dep[x]+1&&(temp=dfs(e[i].to,min(flow,e[i].size)))){e[i].size-=temp;e[e[i].same].size+=temp;return temp;}}return 0;
}
void Dinic(){int flow;while(bfs()){memcpy(cur,head,sizeof head);while((flow=dfs(0,oo))){ans-=flow;}}printf("%d\n",ans);
}int main(){Init();Dinic();return 0;
}