首页 > 代码库 > 洛谷 P2469 [SDOI2010]星际竞速 解题报告

洛谷 P2469 [SDOI2010]星际竞速 解题报告

2024-09-11 11:24:14   219人阅读

题目描述

10年一度的银河系赛车大赛又要开始了。作为全银河最盛大的活动之一，夺得这个项目的冠军无疑是很多人的梦想，来自杰森座α星的悠悠也是其中之一。

赛车大赛的赛场由N颗行星和M条双向星际航路构成，其中每颗行星都有一个不同的引力值。大赛要求车手们从一颗与这N颗行星之间没有任何航路的天体出发，访问这N颗行星每颗恰好一次，首先完成这一目标的人获得胜利。

由于赛制非常开放，很多人驾驶着千奇百怪的自制赛车来参赛。这次悠悠驾驶的赛车名为超能电驴，这是一部凝聚了全银河最尖端科技结晶的梦幻赛车。作为最高科技的产物，超能电驴有两种移动模式：高速航行模式和能力爆发模式。在高速航行模式下，超能电驴会展开反物质引擎，以数倍于光速的速度沿星际航路高速航行。在能力爆发模式下，超能电驴脱离时空的束缚，使用超能力进行空间跳跃——在经过一段时间的定位之后，它能瞬间移动到任意一个行星。

天不遂人愿，在比赛的前一天，超能电驴在一场离子风暴中不幸受损，机能出现了一些障碍：在使用高速航行模式的时候，只能由每个星球飞往引力比它大的星球，否则赛车就会发生爆炸。

尽管心爱的赛车出了问题，但是悠悠仍然坚信自己可以取得胜利。他找到了全银河最聪明的贤者——你，请你为他安排一条比赛的方案，使得他能够用最少的时间完成比赛。

　　　　　　　　　　　　--by luogu

http://daniu.luogu.org/problem/show?pid=2469

一开始，并不知道怎么搞；

后来听说和最小路径覆盖有关，然后就问了博一最小路径覆盖是怎么搞的......然后就把这个题搞出来了；

建图：

  • 拆点
  • S连所有一排点，1流0费；
  • S连所有二排点，1流跳跃的费用（1类边）；
  • 一排点向有路径且可到达的点连边，1流路径费用（2类边）；
  • 所有二排点连T点，1流0费；

由于所有点至少可以跳跃到达，于是最大流为n，保证了遍历；

考虑每个点的花费：

1要么由跳跃到达，这样花费1类边，跳跃不受起点影响，所以可认为是从S跳过来的

2要么由某个点经边到达，这样花费2类边，不管怎样边的起点一定到达过，于是直接从S连一排点，一排点连二排点

对于2，细致的讨论一下：

因为题目说编号对边方向有限制作用，于是不用担心边起点在终点遍历后再遍历

本题与最小路径覆盖的相通之处——把路径拆成一条一条边，由于每条使用时都已经有了充足前置条件，所以可以这样做；

代码如下：（极烂的代码，还是折叠了吧）

#include<cstdio>#include<cstring>#include<algorithm>#define INF 2147483600using namespace std;int n,m,s,t;struct ss{	int next,wi,fi,to,cp;}x[100001];int first[2001];int num;int dis[2001],vis[2001],pre[2001],way[2001],que[100001];int answ,ansf;void build(int ,int ,int ,int );int spfa();void EK();int main(){	int i,j,k,l,o,m;	scanf("%d%d",&n,&m);	s=0,t=n<<1|1;	for(i=1;i<=n;i++){		scanf("%d",&j);		build(s,i+n,1,j);		x[num].cp=num+1;		build(i+n,s,0,-j);		x[num].cp=num-1;		build(s,i,1,0);		x[num].cp=num+1;		build(i,s,0,0);		x[num].cp=num-1;		build(n+i,t,1,0);		x[num].cp=num+1;		build(t,n+i,0,0);		x[num].cp=num-1;	}	for(i=1;i<=m;i++){		scanf("%d%d%d",&j,&k,&o);		if(j>k)			swap(j,k);		build(j,n+k,1,o);		x[num].cp=num+1;		build(n+k,j,0,-o);		x[num].cp=num-1;	}	while(spfa())		EK();	printf("%d",ansf);	return 0;}void build(int fr,int t,int w,int f){	x[++num].next=first[fr];	x[num].to=t;	x[num].fi=f;	x[num].wi=w;	first[fr]=num;}int spfa(){	int h=0,w=1,i;	for(i=s;i<=t;i++)		dis[i]=2147483647;	memset(vis,0,sizeof(vis));	memset(pre,-1,sizeof(pre));	dis[s]=0;vis[s]=1;	que[w]=s;	while(h<w){		h++;		vis[que[h]]=0;		i=first[que[h]];		while(i){			if(x[i].wi&&dis[x[i].to]>dis[que[h]]+x[i].fi){				dis[x[i].to]=dis[que[h]]+x[i].fi;				pre[x[i].to]=que[h];				way[x[i].to]=i;				if(vis[x[i].to]==0){				  w++;				  que[w]=x[i].to;				  vis[que[w]]=1;			    }			}			i=x[i].next;		}	}	if(dis[t]!=2147483647)return 1;	return 0;}void EK(){	int i=t;	int addf=0,addw=INF;	while(pre[i]!=-1){		if(x[way[i]].wi<addw)			addw=x[way[i]].wi;		i=pre[i];	}	i=t;	while(pre[i]!=-1){		addf+=x[way[i]].fi*addw;		x[way[i]].wi-=addw;		x[x[way[i]].cp].wi+=addw;		i=pre[i];	}	answ+=addw;	ansf+=addf;}

祝AC

 

洛谷 P2469 [SDOI2010]星际竞速 解题报告


联系
我们