1565: [NOI2009]植物大战僵尸
Time Limit: 10 Sec Memory Limit: 64 MB
Submit: 2164 Solved: 1001
[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
10 0
20 0
-10 0
-5 1 0 0
100 1 2 1
100 0
Sample Output
25
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 。
【题解】
这题的麻烦之处在于网络中可能出现环，导致死循环。
首先建图：如果一行之中，有一个植物被在同一行中左边的植物保护，就会形成环，那么我们只需要在每一行的植物向左边一个植物连一条边就行了。然后就是由保护者向被保护者连一条边。
拓扑判环、删点，不再赘述。
重新建图：遍历每个点，如果这个点没被删除，就在新图上保留有这个点出发的所有边。并判断：如果点权为正，从此点向终点连边，否则，由起点向此点连边。顺便记下所有正点权之和sum
求最大流ans后，sum-ans就是答案。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<algorithm>
using namespace std;
#define MAXN 610000
#define INF 1000000000
struct node{int y,next,v,rel;}E[MAXN],e[MAXN];
int n,m,len,S,T,ans,sum,v[MAXN],Link1[MAXN],id[MAXN],q[MAXN],del[MAXN],Link[MAXN],level[MAXN];
inline int read()
{
int x=,f=; char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') f=-; ch=getchar();}
while(isdigit(ch)) {x=x*+ch-''; ch=getchar();}
return x*f;
}
void insert1(int x,int y) {id[y]++;E[++len].next=Link1[x];Link1[x]=len;E[len].y=y;}
void insert2(int x,int y,int v)
{
e[++len].next=Link[x];Link[x]=len;e[len].y=y;e[len].v=v;e[len].rel=len+;
e[++len].next=Link[y];Link[y]=len;e[len].y=x;e[len].v=;e[len].rel=len-;
}
void dfs(int x)
{
del[x]=;
for(int i=Link1[x];i;i=E[i].next)
if(!del[E[i].y]) dfs(E[i].y);
}
void topsort()
{
int head=,tail=;
for(int i=;i<=n*m;i++) if(!id[i]) q[++tail]=i; else del[i]=;
while(++head<=tail)
{
int now=q[head];
del[now]=;
for(int i=Link1[now];i;i=E[i].next)
{
id[E[i].y]--;
if(!id[E[i].y]) q[++tail]=E[i].y;
}
}
for(int i=;i<=n*m;i++) if(del[i]) dfs(i);
}
void build()
{
len=; S=; T=n*m+;
for(int i=;i<=n*m;i++)
if(!del[i])
{
if(v[i]>) {sum+=v[i]; insert2(i,T,v[i]);}
else insert2(S,i,-v[i]);
for(int j=Link1[i];j;j=E[j].next)
if(!del[E[j].y])
insert2(i,E[j].y,INF);
}
}
bool bfs()
{
memset(level,-,sizeof(level));
int head=,tail=;
q[]=S; level[S]=;
while(++head<=tail)
{
for(int i=Link[q[head]];i;i=e[i].next)
if(e[i].v&&level[e[i].y]<)
{
q[++tail]=e[i].y;
level[q[tail]]=level[q[head]]+;
}
}
return level[T]>=;
}
int MAXFLOW(int x,int flow)
{
if(x==T) return flow;
int d=,maxflow=;
for(int i=Link[x];i&&maxflow<flow;i=e[i].next)
if(level[e[i].y]==level[x]+&&e[i].v)
if(d=MAXFLOW(e[i].y,min(e[i].v,flow-maxflow)))
{
maxflow+=d;
e[i].v-=d;
e[e[i].rel].v+=d;
}
if(!maxflow) level[x]=-;
return maxflow;
}
void solve()
{
int d=;
while(bfs())
while(d=MAXFLOW(S,INF))
ans+=d;
}
int main()
{
//freopen("pvz.in","r",stdin);
//freopen("pvz.out","w",stdout);
n=read(); m=read();
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
{
int x=(i-)*m+j;
v[x]=read(); int w=read();
while(w--)
{
int a=read(),b=read();
a++; b++;
int y=(a-)*m+b;
insert1(x,y);
}
}
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
{
int x=(i-)*m+j,y=x-;
insert1(x,y);
}
topsort();
build();
solve();
printf("%d\n",sum-ans);
return ;
}