1927: [Sdoi2010]星际竞速
Time Limit: 20 Sec Memory Limit: 259 MBSubmit: 1651 Solved: 1006
[Submit][Status][Discuss]
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更优,但我们却不能那样做,因为
那会导致超能电驴爆炸。
对于 30%的数据 N≤20,M≤50;
对于 70%的数据 N≤200,M≤4000;
对于100%的数据N≤800, M≤15000。输入数据中的任何数都不会超过106
。
输入数据保证任意两颗行星之间至多存在一条航道,且不会存在某颗行星到
自己的航道。
Source
首先将每个星球裂成两个点,源连第一个点流量为1费用为0,第二个点连汇流量为1费用为0,这样就保证每个点经过且仅经过一次。然后边就从第一个点连向第二个点流量1费用边权,瞬移就从源连向第二个点流量1费用权值。
代码:
#include<cstdio> #include<cstring> #include<algorithm> #define INF 1000000000 using namespace std; int n,m,u,v,w,edgenum,ans; int vet[500010],next[500010],head[500010],maxv[500010],cost[500010],dis[500010],flag[500010],q[500010],last[500010],pre[500010],a[500010]; void add(int u,int v,int w1,int w2) { vet[++edgenum]=v; next[edgenum]=head[u]; head[u]=edgenum; maxv[edgenum]=w1; cost[edgenum]=w2; } void spfa() { for (int i=1;i<=2*n+1;i++) dis[i]=INF; dis[0]=0; memset(flag,0,sizeof(flag)); int p1=-1,p2=0; q[0]=0; flag[0]=1; while (p1<p2) { u=q[++p1]; flag[u]=0; for (int e=head[u];e;e=next[e]) { int v=vet[e]; if (maxv[e]>0&&dis[u]+cost[e]<dis[v]) { dis[v]=dis[u]+cost[e]; last[v]=e; pre[v]=u; if (!flag[v]){flag[v]=1;q[++p2]=v;} } } } } void work() { int t=2*n+1; while (t!=0) { maxv[last[t]]--; if (last[t]&1) maxv[last[t]+1]++;else maxv[last[t]-1]++; t=pre[t]; } } int main() { scanf("%d%d",&n,&m); for (int i=1;i<=n;i++) scanf("%d",&a[i]); for (int i=1;i<=m;i++) { scanf("%d%d%d",&u,&v,&w); if (u>v) swap(u,v); add(u,v+n,1,w);add(v+n,u,0,-w); } for (int i=1;i<=n;i++) { add(0,i,1,0);add(i,0,0,0); add(i+n,n*2+1,1,0);add(n*2+1,i+n,0,0); } for (int i=1;i<=n;i++){add(0,i+n,1,a[i]);add(i+n,0,0,-a[i]);} while (1) { spfa(); if (dis[n*2+1]==INF) break; ans+=dis[n*2+1]; work(); } printf("%d\n",ans); }