bzoj1927 [Sdoi2010]星际竞速

bzoj1927 [Sdoi2010]星际竞速

​​ Description

10年一度的银河系赛车大赛又要开始了。作为全银河最盛大的活动之一，夺得这个项目的冠军无疑是很多人的 梦想，来自杰森座α星的悠悠也是其中之一。赛车大赛的赛场由N颗行星和M条双向星际航路构成，其中每颗行星都 有一个不同的引力值。大赛要求车手们从一颗与这N颗行星之间没有任何航路的天体出发，访问这N颗行星每颗恰好 一次，首先完成这一目标的人获得胜利。由于赛制非常开放，很多人驾驶着千奇百怪的自制赛车来参赛。这次悠悠 驾驶的赛车名为超能电驴，这是一部凝聚了全银河最尖端科技结晶的梦幻赛车。作为最高科技的产物，超能电驴有 两种移动模式：高速航行模式和能力爆发模式。在高速航行模式下，超能电驴会展开反物质引擎，以数倍于光速的 速度沿星际航路高速航行。在能力爆发模式下，超能电驴脱离时空的束缚，使用超能力进行空间跳跃——在经过一 段时间的定位之后，它能瞬间移动到任意一个行星。天不遂人愿，在比赛的前一天，超能电驴在一场离子风暴中不 幸受损，机能出现了一些障碍：在使用高速航行模式的时候，只能由每个星球飞往引力比它大的星球，否则赛车就 会发生爆炸。尽管心爱的赛车出了问题，但是悠悠仍然坚信自己可以取得胜利。他找到了全银河最聪明的贤者—— 你，请你为他安排一条比赛的方案，使得他能够用最少的时间完成比赛。 Input

第一行是两个正整数N,M。第二行N个数A1~AN，其中Ai表示使用能力爆发模式到达行星i所需的定位时间。接下 来M行，每行3个正整数ui,vi,wi，表示在编号为ui和vi的行星之间存在一条需要航行wi时间的星际航路。输入数据 已经按引力值排序，也就是编号小的行星引力值一定小，且不会有两颗行星引力值相同。 Output

仅包含一个正整数，表示完成比赛所需的最少时间。 Sample Input 3 3 1 100 100 2 1 10 1 3 1 2 3 1 Sample Output 12 HINT

说明：先使用能力爆发模式到行星1，花费时间1。然后切换到高速航行模式，航行到行星2，花费时间10。之

后继续航行到行星3完成比赛，花费时间1。虽然看起来从行星1到行星3再到行星2更优，但我们却不能那样做，因

为那会导致超能电驴爆炸。N≤800，M≤15000。输入数据中的任何数都不会超过106。输入数据保证任意两颗行星

之间至多存在一条航道，且不会存在某颗行星到自己的航道。 Source

第一轮Day2

题意：求一条路线可以满足遍历图中的n个点恰好一次 首先看到这个 可能脑子里率先就是拆点上下界最小费用流 但是会T 取膜了 题解 看了发现我可以确定的是我一定是从引力下的地方指向引力大的地方 然后这样的话就可以看作一个DAG了 但是可能会说为什么没有考虑可以使用另外一种技能的情况啊 是啊 可以抽象的看作我首先从这个点跳到我开始的“起点”然后再从起点重新出发 那么这样来是不是就是最小权值路径覆盖问题了呢首先 拆点 每个点拆成入点和出点 源点向每个点的入点连权值为1 费用为0的边 然后如果有关联 从小连向大连权值为1 费用为时间的边 然后从源连向每个节点的出点连 容量1 费用为瞬间转移时间的边 然后 每个点出点向汇连容量1费用0的点

为什么这样做是对的 因为每个点的出点可以看作是这个点的最终结束状态 我是从前面一个转移过来还是我转移到别人那里重新开始新的一段

#include#include#include#include#define inf 0x3f3f3f3f#define N 2000using namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0;char ch=gc(); while(ch<'0'||ch>'9') ch=gc(); while(ch<='9'&&ch>='0') x=x*10+ch-'0',ch=gc();return x;}int num=1,h[N],f[N],pre[N],path[N],T,n,m;bool flag[N];struct node{ int y,z,next,c;}data[44000];inline void insert1(int x,int y,int z,int c){ data[++num].y=y;data[num].z=z;data[num].next=h[x];h[x]=num;data[num].c=c; data[++num].y=x;data[num].z=0;data[num].next=h[y];h[y]=num;data[num].c=-c;}inline bool spfa(){ memset(f,0x3f,sizeof(f));memset(pre,-1,sizeof(pre));dequeq;q.push_back(0);flag[0]=1;f[0]=0; while(!q.empty()){ int x=q.front();q.pop_front();flag[x]=0; for (int i=h[x];i;i=data[i].next){ int y=data[i].y,z=data[i].z,c=data[i].c; if(f[x]+cy) swap(x,y);insert1(x,y+n,1,read()); } for (int i=1;i<=n;++i) insert1(0,i,1,0),insert1(i+n,T,1,0);int ans=0; while(spfa()){ int minn=inf,now=T; while(now) minn=min(minn,data[path[now]].z),now=pre[now];now=T;ans+=f[T]*minn; while(now) {data[path[now]].z-=minn;data[path[now]^1].z+=minn;now=pre[now];} }printf("%d",ans); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。