「BZOJ1927」[SDOI2010] 星际竞速
题目描述 Description
10 年一度的银河系赛车大赛又要开始了。作为全银河最盛大的活动之一，夺得这个项目的冠军无疑是很多人的梦想，来自杰森座 α星的悠悠也是其中之一。
赛车大赛的赛场由 N 颗行星和M条双向星际航路构成，其中每颗行星都有一个不同的引力值。大赛要求车手们从一颗与这 N 颗行星之间没有任何航路的天体出发，访问这 N 颗行星每颗恰好一次，首先完成这一目标的人获得胜利。
由于赛制非常开放，很多人驾驶着千奇百怪的自制赛车来参赛。这次悠悠驾驶的赛车名为超能电驴，这是一部凝聚了全银河最尖端科技结晶的梦幻赛车。作为最高科技的产物，超能电驴有两种移动模式：高速航行模式和能力爆发模式。在高速航行模式下，超能电驴会展开反物质引擎，以数倍于光速的速度沿星际航路高速航行。在能力爆发模式下，超能电驴脱离时空的束缚，使用超能力进行空间跳跃——在经过一段时间的定位之后，它能瞬间移动到任意一个行星。
天不遂人愿，在比赛的前一天，超能电驴在一场离子风暴中不幸受损，机能出现了一些障碍：在使用高速航行模式的时候，只能由每个星球飞往引力比它大的星球，否则赛车就会发生爆炸。
尽管心爱的赛车出了问题，但是悠悠仍然坚信自己可以取得胜利。他找到了全银河最聪明的贤者——你，请你为他安排一条比赛的方案，使得他能够用最少的时间完成比赛。
输入描述 Input Description
第一行是两个正整数 N, M。
第二行 N 个数 A1~AN， 其中Ai表示使用能力爆发模式到达行星 i 所需的定位
时间。
接下来 M行，每行 3个正整数ui, vi, wi，表示在编号为 ui和vi的行星之间存在一条需要航行wi时间的星际航路。
输入数据已经按引力值排序，也就是编号小的行星引力值一定小，且不会有两颗行星引力值相同。
输出描述 Output Description
仅包含一个正整数，表示完成比赛所需的最少时间。
样例输入 Sample Input
3 3
1 100 100
2 1 10
1 3 1
2 3 1
样例输出 Sample Output
12
数据范围及提示 Data Size & Hint
对于 30%的数据 N≤20，M≤50；
对于 70%的数据 N≤200，M≤4000；
对于100%的数据N≤800， M≤15000。输入数据中的任何数都不会超过106
。
输入数据保证任意两颗行星之间至多存在一条航道，且不会存在某颗行星到
自己的航道。
拆点+费用流 类似最小路径覆盖
2014.9.21
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> #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 n,m,T,cnt=1,ans; int a[1605],last[1605],q[1605],dis[1605],from[1605]; bool inq[1605]; struct data{int to,next,from,v,c;}e[3000005]; void ins(int u,int v,int w,int c) { e[++cnt].to=v;e[cnt].next=last[u];e[cnt].from=u;last[u]=cnt;e[cnt].v=w;e[cnt].c=c; } void insert(int u,int v,int w,int c) { ins(u,v,w,c); ins(v,u,0,-c); } bool spfa() { for(int i=0;i<=T;i++)dis[i]=inf; int head=0,tail=1; dis[0]=0;q[0]=0;inq[0]=1; while(head!=tail) { int now=q[head++];if(head==1601)head=0; for(int i=last[now];i;i=e[i].next) if(e[i].v&&e[i].c+dis[now]<dis[e[i].to]) { dis[e[i].to]=e[i].c+dis[now]; from[e[i].to]=i; if(!inq[e[i].to]) { inq[e[i].to]=1; if(dis[e[i].to]<dis[q[head]]) { head--;if(head==-1)head=1600; q[head]=e[i].to; } else { q[tail++]=e[i].to; if(tail==1601)tail=0; } } } inq[now]=0; } if(dis[T]==inf)return 0; return 1; } void mcf() { int x=inf; for(int i=from[T];i;i=from[e[i].from]) x=min(e[i].v,x); for(int i=from[T];i;i=from[e[i].from]) { ans+=x*e[i].c; e[i].v-=x;e[i^1].v+=x; } } int main() { n=read();m=read();T=2*n+1; for(int i=1;i<=n;i++)a[i]=read(); for(int i=1;i<=n;i++) { insert(0,i,1,0); insert(i+n,T,1,0); insert(0,i+n,1,a[i]); } for(int i=1;i<=m;i++) { int u=read(),v=read(),w=read(); if(u>v)swap(u,v); insert(u,v+n,1,w); } while(spfa())mcf(); printf("%d\n",ans); return 0; } |
2015.2.5 zkw费用流
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 |
#include<map> #include<cmath> #include<queue> #include<vector> #include<stack> #include<cstdlib> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long #define inf 1000000000 using namespace std; 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 T,n,m,cnt=1,ans; int last[2005],dis[2005],q[2005]; bool mark[2005],inq[2005]; struct edge{ int to,next,v,c; }e[2000005]; void insert(int u,int v,int w,int c) { e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;e[cnt].v=w;e[cnt].c=c; e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt;e[cnt].v=0;e[cnt].c=-c; } bool spfa() { int head=0,tail=1; for(int i=0;i<=T;i++)dis[i]=inf; memset(inq,0,sizeof(inq)); dis[T]=0;q[0]=T;inq[T]=1; while(head!=tail) { int now=q[head];head++;inq[now]=0; if(head==2005)head=0; for(int i=last[now];i;i=e[i].next) if(dis[now]-e[i].c<dis[e[i].to]&&e[i^1].v) { dis[e[i].to]=dis[now]-e[i].c; if(!inq[e[i].to]) { inq[e[i].to]=1; q[tail++]=e[i].to; if(tail==2005)tail=0; } } } return dis[0]!=inf; } int dfs(int x,int f) { mark[x]=1; if(x==T)return f; int w,used=0; for(int i=last[x];i;i=e[i].next) { if(e[i].v&&!mark[e[i].to]&&dis[x]-e[i].c==dis[e[i].to]) { w=dfs(e[i].to,min(e[i].v,f-used)); e[i].v-=w;e[i^1].v+=w; ans+=e[i].c*w; used+=w;if(used==f)return f; } } return used; } int zkw() { int tmp=0; while(spfa()) { mark[T]=1; while(mark[T]) { memset(mark,0,sizeof(mark)); tmp+=dfs(0,inf); } } return tmp; } int main() { n=read();m=read();T=2*n+1; for(int i=1;i<=n;i++) { int t=read(); insert(0,i,1,0); insert(i+n,T,1,0); insert(0,i+n,1,t); } for(int i=1;i<=m;i++) { int u=read(),v=read(),c=read(); if(u>v)swap(u,v); insert(u,v+n,1,c); } zkw(); printf("%d",ans); return 0; } |
计数器 9852443
OI 课件=>
OI 课件=>
请问黄学长为何不要点两两之间连一条i->j+n的费用为a
的边
最终的解肯定是若干次高速航行，然后能力爆发跳回某个点，然后再高速航行
可以看做每次能力爆发都从S开始；
而且显然你加入这样的边不会使得流的结果发生变化
可是您这么建图不应该源点向每个点连一条流量为INF，费用为a
的边吗，因为它可以回到这个点很多次啊……
题目要求 恰好一次
soga……谢谢黄学长了……
请问黄学长，if(dis[e[i].to]<dis[q[head]])这句是什么优化？
SLF优化