「BZOJ1822」[JSOI2010] Frozen Nova 冷冻波

2014年12月15日4,7366

Description

WJJ喜欢“魔兽争霸”这个游戏。在游戏中，巫妖是一种强大的英雄，它的技能Frozen Nova每次可以杀死一个小精灵。我们认为，巫妖和小精灵都可以看成是平面上的点。当巫妖和小精灵之间的直线距离不超过R，且巫妖看到小精灵的视线没有被树木阻挡（也就是说，巫妖和小精灵的连线与任何树木都没有公共点）的话，巫妖就可以瞬间杀灭一个小精灵。在森林里有N个巫妖，每个巫妖释放Frozen Nova之后，都需要等待一段时间，才能再次施放。不同的巫妖有不同的等待时间和施法范围，但相同的是，每次施放都可以杀死一个小精灵。现在巫妖的头目想知道，若从0时刻开始计算，至少需要花费多少时间，可以杀死所有的小精灵？

Input

输入文件第一行包含三个整数N、M、K(N,M,K<=200)，分别代表巫妖的数量、小精灵的数量和树木的数量。接下来N行，每行包含四个整数x, y, r, t，分别代表了每个巫妖的坐标、攻击范围和施法间隔（单位为秒）。再接下来M行，每行两个整数x, y，分别代表了每个小精灵的坐标。再接下来K行，每行三个整数x, y, r，分别代表了每个树木的坐标。输入数据中所有坐标范围绝对值不超过10000，半径和施法间隔不超过20000。

Output

输出一行，为消灭所有小精灵的最短时间（以秒计算）。如果永远无法消灭所有的小精灵，则输出-1。

Sample Input

2 3 1
-100 0 100 3
100 0 100 5
-100 -10
100 10
110 11
5 5 10

Sample Output

题解

二分时间，计算几何判断每个巫师可以攻击到哪些精灵，网络流判定

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<cstring>
#define ll long long 
#define inf 1000000000
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 ans;
int n,m,K,cnt,T;
int d[205],r[205],tim[205],last[405];
int tr[205];
int h[405],q[405],cur[405];
int mp[205][205];
struct edge{
	int to,next,v;
}e[500005];
struct P{
	int x,y;
}w[205],t[205],s[205];
struct L{
	P a,b;
};
void insert(int u,int v,int w)
{
	e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;e[cnt].v=w;
	e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt;e[cnt].v=0;
}
inline P operator-(P a,P b)
{
	P t;t.x=a.x-b.x;t.y=a.y-b.y;return t;
}
inline double operator*(P a,P b)
{
	return a.x*b.y-a.y*b.x;
}
inline double dot(P a,P b)
{
	return a.x*b.x+a.y*b.y;
}
inline double dis(P a,P b)
{
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
inline double dis(L l,P p)
{
	if(dot(l.a-p,l.b-p)>0)
		return min(dis(l.a,p),dis(l.b,p));
	return abs((p-l.a)*(l.b-l.a)/dis(l.a,l.b));
}
bool jud(int x,int y)//巫妖x与精灵y
{
	if(dis(w[x],s[y])>r[x])return 0;
	for(int i=1;i<=K;i++)
		if(dis((L){w[x],s[y]},t[i])<tr[i])return 0;
	return 1;
}
void build(int x)
{
	cnt=1;
	for(int i=1;i<=cnt;i++)e[i].v=0;
	T=n+m+1;
	memset(last,0,sizeof(last));
	for(int i=1;i<=n;i++)
		insert(0,i,x/tim[i]+1);
	for(int i=1;i<=m;i++)
		insert(i+n,T,1);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(mp[i][j])insert(i,j+n,1);
}
bool bfs()
{
	int head=0,tail=1;
	for(int i=0;i<=T;i++)h[i]=-1;
	q[0]=0;h[0]=0;
	while(head!=tail)
	{
		int now=q[head];head++;
		for(int i=last[now];i;i=e[i].next)
			if(e[i].v&&h[e[i].to]==-1)
			{
				h[e[i].to]=h[now]+1;
				q[tail++]=e[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=e[i].next)
		if(h[e[i].to]==h[x]+1)
		{
			w=f-used;
			w=dfs(e[i].to,min(w,e[i].v));
			e[i].v-=w;e[i^1].v+=w;
			if(e[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]=last[i];
		ans+=dfs(0,inf);
	}
}
int main()
{
	int mx=0;
	n=read();m=read();K=read();
	for(int i=1;i<=n;i++)
		w[i].x=read(),w[i].y=read(),r[i]=read(),tim[i]=read(),mx=max(mx,tim[i]);
	for(int i=1;i<=m;i++)
		s[i].x=read(),s[i].y=read();
	for(int i=1;i<=K;i++)
		t[i].x=read(),t[i].y=read(),tr[i]=read();
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			mp[i][j]=jud(i,j);
			if(mp[i][j])d[j]=1;
		}
	for(int i=1;i<=m;i++)
		if(!d[i])
		{
			puts("-1");
			return 0;
		}
	int l=0,r=m*mx,mid;
	while(l<=r)
	{
		mid=(l+r)>>1;
		build(mid);
		ans=0;
		dinic();
		if(ans==m)r=mid-1;
		else l=mid+1;
	}
	printf("%d\n",l);
	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

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<algorithm>

#include<cmath>

#include<cstring>

#define ll long long

#define inf 1000000000

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 ans;

int n,m,K,cnt,T;

int d[205],r[205],tim[205],last[405];

int tr[205];

int h[405],q[405],cur[405];

int mp[205][205];

struct edge{

int to,next,v;

}e[500005];

struct P{

int x,y;

}w[205],t[205],s[205];

struct L{

P a,b;

};

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

{

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

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

}

inline P operator-(P a,P b)

{

P t;t.x=a.x-b.x;t.y=a.y-b.y;return t;

}

inline double operator*(P a,P b)

{

return a.x*b.y-a.y*b.x;

}

inline double dot(P a,P b)

{

return a.x*b.x+a.y*b.y;

}

inline double dis(P a,P b)

{

return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));

}

inline double dis(L l,P p)

{

if(dot(l.a-p,l.b-p)>0)

return min(dis(l.a,p),dis(l.b,p));

return abs((p-l.a)*(l.b-l.a)/dis(l.a,l.b));

}

bool jud(int x,int y)//巫妖x与精灵y

{

if(dis(w[x],s[y])>r[x])return 0;

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

if(dis((L){w[x],s[y]},t[i])<tr[i])return 0;

return 1;

}

void build(int x)

{

cnt=1;

for(int i=1;i<=cnt;i++)e[i].v=0;

T=n+m+1;

memset(last,0,sizeof(last));

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

insert(0,i,x/tim[i]+1);

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

insert(i+n,T,1);

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

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

if(mp[i][j])insert(i,j+n,1);

}

bool bfs()

{

int head=0,tail=1;

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

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

while(head!=tail)

{

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

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

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

{

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

q[tail++]=e[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=e[i].next)

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

{

w=f-used;

w=dfs(e[i].to,min(w,e[i].v));

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

if(e[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]=last[i];

ans+=dfs(0,inf);

}

int main()

{

int mx=0;

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

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

w[i].x=read(),w[i].y=read(),r[i]=read(),tim[i]=read(),mx=max(mx,tim[i]);

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

s[i].x=read(),s[i].y=read();

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

t[i].x=read(),t[i].y=read(),tr[i]=read();

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

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

{

mp[i][j]=jud(i,j);

if(mp[i][j])d[j]=1;

}

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

if(!d[i])

{

puts("-1");

return 0;

}

int l=0,r=m*mx,mid;

while(l<=r)

{

mid=(l+r)>>1;

build(mid);

ans=0;

dinic();

if(ans==m)r=mid-1;

else l=mid+1;

}

printf("%d\n",l);

return 0;

}

« 「BZOJ2348」[Baltic 2011] Plagiarism 「CF497B」Tennis Game »

Lesphere

题上说不能有任何公共点,好像巫妖与精灵的连线与树木所在圆相切是可以的?
还有您的点到线段距离为何这样写,题目数据有问题?

Lesphere

我又打错网络流,但数据确实够水的

HugeG

%%%lesphere

hzwer

这个写法有什么问题么。。。

Lesphere

若点P与线段AB,成以∠APB为钝角的三角形,dot>0,不就有问题

不能以∠APB是否为钝角为依据应该是判断∠PAB 或∠PBA是否为钝角

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

「BZOJ1822」[JSOI2010] Frozen Nova 冷冻波

Description

Input

Output

Sample Input

Sample Output

题解

分类目录

热门文章

Myfriends

近期评论