SGU438 The Glorious Karlutka River =)

传送门

sgu原来搬到cf了呀点了好几个链接才找到233

传说中的动态流（？）

反正很暴力就对了QwQ

有容量限制->拆点对于每个点拆成入点和出点

时间限制->分层对于每个时刻的每个石头都建点

所以源点连最开始的到达的石头的入点然后每个可以到达的出点连汇点

然后每个时刻的入点出点之间连接流量为C 然后可以互相跳的连inf

枚举时刻在残存网络上继续流可以了直到一个时刻 >=m 就是所有人都跳过去了QwQ

附代码。

我觉得我这份代码巨好看（大雾）

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#include<queue>

#define inf 20021225

#define ll long long

#define mxn 42010

#define mxm 960010

using namespace std;

queue<int> que;

struct point{int x,y,c;}p[51];

struct edge{int to,lt,f;}e[mxm<<1];

int in[mxn],cnt=1,dep[mxn],s,t,n,m,d,w;

void add(int x,int y,int f){e[++cnt].to=y;e[cnt].lt=in[x];e[cnt].f=f;in[x]=cnt;}

void addedge(int x,int y,int f){add(x,y,f);add(y,x,0);}

bool bfs()

{

	while(!que.empty())	que.pop();

	memset(dep,0,sizeof(dep));

	dep[s]=1;que.push(s);

	while(!que.empty())

	{

		int x=que.front();que.pop();

		for(int i=in[x];i;i=e[i].lt)

		{

			int y=e[i].to;

			if(!dep[y]&&e[i].f)

			{

				dep[y]=dep[x]+1;

				if(y==t)	return 1;

				que.push(y);

			}

		}

	}

	return 0;

}

int dfs(int x,int flow)

{

	if(x==t||!flow)	return flow;

	int cur=flow;

	for(int i=in[x];i;i=e[i].lt)

	{

		int y=e[i].to;

		if(dep[y]==dep[x]+1&&e[i].f)

		{

			int tmp=dfs(y,min(cur,e[i].f));

			cur-=tmp;e[i].f-=tmp;e[i^1].f+=tmp;

			if(!cur)	return flow;

		}

	}

	dep[x]=-1;

	return flow-cur;

}

int dinic()

{

	int ans=0;

	while(bfs())

		ans+=dfs(s,inf);

		//printf("%d\n",ans);

	return ans;

}

int id(int x,int dep){return dep*m+x;}

int dis(point a,point b){return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);}

bool jump(point a,point b){return dis(a,b)<=d*d;}

bool st[51],fn[51];

int main()

{

	scanf("%d%d%d%d",&n,&m,&d,&w);

	s=mxn-4;t=s+1;

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

	{

		scanf("%d%d%d",&p[i].x,&p[i].y,&p[i].c);

		if(p[i].y<=d)	st[i]=1;

		if(p[i].y>=w-d)	fn[i]=1;

	}

	if(w<=d){printf("1\n");return 0;}

	int tot=0,tm;

	for(tm=0;tm<n+m;tm++)

	{

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

		{

			if(st[i])	addedge(s,id(i,tm<<1),inf);

			if(fn[i])	addedge(id(i,tm<<1|1),t,inf);

			addedge(id(i,tm<<1),id(i,tm<<1|1),p[i].c);

		}

		tot+=dinic();

		if(tot>=m)	break;

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

		{

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

			{

				if(i==j)	continue;

				if(jump(p[i],p[j]))	addedge(id(i,tm<<1|1),id(j,tm+1<<1),inf);

			}

		}

	}

	if(tm<n+m)	printf("%d\n",tm+2);

	else	printf("IMPOSSIBLE\n");

	return 0;

}

巴特西

SGU438 The Glorious Karlutka River =)

传送门

最新文章

热门文章