NOI2009植物大战僵尸

2014年12月17日6,2960

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 。

题解

若a保护b，则a向b连边

发现保护关系若形成环，则环以及环间接保护都不可攻击

删去这些点，然后就是最大权闭合子图模型

若v[x]<0 S->x 权-v[x]

否则 x-T 权v[x]

若a保护b则 a-> b 权inf

答案是正权和-flow

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<set>
#include<ctime>
#include<vector>
#include<queue>
#include<algorithm>
#include<map>
#define pa pair<int,int>
#define inf 1000000000
#define ll long long 
#define p(x,y) (x-1)*m+y
using namespace std;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,m,T;
int tot,top,cnt,ans;
int v[605],cur[605],h[605],d[605],q[605];
bool del[605];
struct edge{
	int to,next,v;
}e[400005],ed[800005];int last[605],last2[605];
void insert(int u,int v)
{
	d[v]++;
	e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;
}
void insert2(int u,int v,int w)
{
	ed[++cnt].to=v;ed[cnt].next=last2[u];last2[u]=cnt;ed[cnt].v=w;
	ed[++cnt].to=u;ed[cnt].next=last2[v];last2[v]=cnt;ed[cnt].v=0;
}
void dfs(int x)
{
	del[x]=1;
	for(int i=last[x];i;i=e[i].next)
		if(!del[e[i].to])dfs(e[i].to);
}
void topsort()
{
	for(int i=1;i<=n*m;i++)
		if(!d[i])q[++top]=i;
		else del[i]=1;
	while(top)
	{
		int now=q[top];del[now]=0;
		top--;
		for(int i=last[now];i;i=e[i].next)
		{
			d[e[i].to]--;
			if(!d[e[i].to])q[++top]=e[i].to;
		}
	}
	for(int i=1;i<=n*m;i++)
		if(del[i])dfs(i);
}
void rebuild()
{
	cnt=1;T=n*m+1;
	for(int x=1;x<=n*m;x++)
		if(!del[x])
		{
			if(v[x]>0)tot+=v[x],insert2(x,T,v[x]);
			else insert2(0,x,-v[x]);
			for(int i=last[x];i;i=e[i].next)
				if(!del[e[i].to])
					insert2(x,e[i].to,inf);
		}  
}
bool bfs()
{
	int head=0,tail=1;
	for(int i=0;i<=T;i++)h[i]=-1;
	h[0]=0;q[0]=0;
	while(head!=tail)
	{
		int now=q[head];head++;
		for(int i=last2[now];i;i=ed[i].next)
			if(ed[i].v&&h[ed[i].to]==-1)
			{
				h[ed[i].to]=h[now]+1;
				q[tail++]=ed[i].to;
			}
	}
	return h[T]!=-1;
}
int dfs(int x,int f)
{
	if(x==T)return f;
	int w,used=0;
	for(int i=cur[x];i;i=ed[i].next)
		if(h[ed[i].to]==h[x]+1)
		{
			w=dfs(ed[i].to,min(ed[i].v,f-used));
			ed[i].v-=w;ed[i^1].v+=w;
			if(ed[i].v)cur[x]=i;
			used+=w;if(used==f)return f;
		}
	if(!used)h[x]=-1;
	return used;
}
void dinic()
{
	while(bfs())
	{
		for(int i=0;i<=T;i++)cur[i]=last2[i];
		ans+=dfs(0,inf);
	}
}
int main()
{
	n=read();m=read();
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			v[p(i,j)]=read();
			int x=read();
			while(x--)
			{
				int a=read(),b=read();
				a++;b++;
				insert(p(i,j),p(a,b)); 
			}
		}
	for(int i=1;i<=n;i++)
		for(int j=m;j>1;j--)
			insert(p(i,j),p(i,j-1));
	topsort();
	rebuild();
	dinic();
	printf("%d",tot-ans);
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<set>

#include<ctime>

#include<vector>

#include<queue>

#include<algorithm>

#include<map>

#define pa pair<int,int>

#define inf 1000000000

#define ll long long

#define p(x,y) (x-1)*m+y

using namespace std;

inline int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n,m,T;

int tot,top,cnt,ans;

int v[605],cur[605],h[605],d[605],q[605];

bool del[605];

struct edge{

int to,next,v;

}e[400005],ed[800005];int last[605],last2[605];

void insert(int u,int v)

{

d[v]++;

e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;

}

void insert2(int u,int v,int w)

{

ed[++cnt].to=v;ed[cnt].next=last2[u];last2[u]=cnt;ed[cnt].v=w;

ed[++cnt].to=u;ed[cnt].next=last2[v];last2[v]=cnt;ed[cnt].v=0;

}

void dfs(int x)

{

del[x]=1;

for(int i=last[x];i;i=e[i].next)

if(!del[e[i].to])dfs(e[i].to);

}

void topsort()

{

for(int i=1;i<=n*m;i++)

if(!d[i])q[++top]=i;

else del[i]=1;

while(top)

{

int now=q[top];del[now]=0;

top--;

for(int i=last[now];i;i=e[i].next)

{

d[e[i].to]--;

if(!d[e[i].to])q[++top]=e[i].to;

}

for(int i=1;i<=n*m;i++)

if(del[i])dfs(i);

}

void rebuild()

{

cnt=1;T=n*m+1;

for(int x=1;x<=n*m;x++)

if(!del[x])

{

if(v[x]>0)tot+=v[x],insert2(x,T,v[x]);

else insert2(0,x,-v[x]);

for(int i=last[x];i;i=e[i].next)

if(!del[e[i].to])

insert2(x,e[i].to,inf);

}

bool bfs()

{

int head=0,tail=1;

for(int i=0;i<=T;i++)h[i]=-1;

h[0]=0;q[0]=0;

while(head!=tail)

{

int now=q[head];head++;

for(int i=last2[now];i;i=ed[i].next)

if(ed[i].v&&h[ed[i].to]==-1)

{

h[ed[i].to]=h[now]+1;

q[tail++]=ed[i].to;

}

return h[T]!=-1;

}

int dfs(int x,int f)

{

if(x==T)return f;

int w,used=0;

for(int i=cur[x];i;i=ed[i].next)

if(h[ed[i].to]==h[x]+1)

{

w=dfs(ed[i].to,min(ed[i].v,f-used));

ed[i].v-=w;ed[i^1].v+=w;

if(ed[i].v)cur[x]=i;

used+=w;if(used==f)return f;

}

if(!used)h[x]=-1;

return used;

}

void dinic()

{

while(bfs())

{

for(int i=0;i<=T;i++)cur[i]=last2[i];

ans+=dfs(0,inf);

}

int main()

{

n=read();m=read();

for(int i=1;i<=n;i++)

for(int j=1;j<=m;j++)

{

v[p(i,j)]=read();

int x=read();

while(x--)

{

int a=read(),b=read();

a++;b++;

insert(p(i,j),p(a,b));

}

for(int i=1;i<=n;i++)

for(int j=m;j>1;j--)

insert(p(i,j),p(i,j-1));

topsort();

rebuild();

dinic();

printf("%d",tot-ans);

return 0;

}

« NOI2010海拔「泉七培训 – 杨国烨」图 »

hzwer.com _ Home | http://hzwer.com

NOI2009植物大战僵尸

Description

Input

Output

Sample Input

Sample Output

HINT

题解

分类目录

热门文章

Myfriends

近期评论