Source: SDOI2010 Round 1,Day 2,Problem 3.
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
starrace.in
3 3
1 100 100
2 1 10
1 3 1
2 3 1
1 100 100
2 1 10
1 3 1
2 3 1
Sample Output
starrace.out
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。输入数据中的任何数都不会超过10^6。
输入数据保证任意两颗行星之间至多存在一条航道，且不会存在某颗行星到自己的航道。
虽说是双向边，但是实际上还是单向的。
将一个点拆成两个
源点向每个点的入点连一条容量为1费用为0的边。
源点向每个点的出点连一条容量为1费用为瞬移到该点所需时间的边。
每个点的出点向汇点连一条容量为1费用为0的边。
对于每条边(i,j)，从i点入点向j点出点连一条容量为1费用为航路所需时间的边。
然后跑费用流就好了
PS:我在bzoj和cogs A了但是在洛谷被卡了一个点 只有90
1 #include<queue> 2 #include<cstdio> 3 #include<cstring> 4 #include<iostream> 5 #define MAXN 150010 6 7 using namespace std; 8 9 const int N=810; 10 const int INF=0x7fffffff; 11 12 struct edge { 13 int to; 14 int next; 15 int val; 16 int fee; 17 }; 18 edge w[MAXN]; 19 20 int head[MAXN],tot=1; 21 22 int n,m,a,b,c,src,decc; 23 24 int flow[N<<1],dis[N<<1],pre[N<<1]; 25 26 bool vis[N<<1]; 27 28 queue<int> Q; 29 30 inline void read(int&x) { 31 int f=1;x=0;char c=getchar(); 32 while(c>'9'||c<'0') {if(c=='-') f=-1;c=getchar();} 33 while(c>='0'&&c<='9') {x=(x<<1)+(x<<3)+c-48;c=getchar();} 34 x=x*f; 35 } 36 37 inline void add(int x,int y,int z,int f) { 38 w[++tot].to=y; 39 w[tot].fee=f; 40 w[tot].val=z; 41 w[tot].next=head[x]; 42 head[x]=tot; 43 } 44 45 inline void add_edge(int x,int y,int z,int f) { 46 add(x,y,z,f); 47 add(y,x,0,-f); 48 } 49 50 inline int change() { 51 for(int i=pre[decc];i;i=pre[w[i^1].to]) { 52 w[i].val-=flow[decc]; 53 w[i^1].val+=flow[decc]; 54 } 55 return dis[decc]*flow[decc]; 56 } 57 58 inline bool spfa() { 59 for(int i=1;i<=n*2+1;i++) vis[i]=false,pre[i]=-1,dis[i]=flow[i]=INF; 60 while(!Q.empty()) Q.pop(); 61 Q.push(src); 62 dis[src]=0; 63 vis[src]=true; 64 pre[src]=0; 65 while(!Q.empty()) { 66 int u=Q.front(); 67 Q.pop(); 68 vis[u]=false; 69 for(int i=head[u];i!=-1;i=w[i].next) { 70 int to=w[i].to; 71 if(dis[to]>dis[u]+w[i].fee&&w[i].val) { 72 dis[to]=dis[u]+w[i].fee; 73 flow[to]=min(flow[to],w[i].val); 74 pre[to]=i; 75 if(!vis[to]) { 76 Q.push(to); 77 vis[to]=true; 78 } 79 } 80 } 81 } 82 return dis[decc]!=INF; 83 } 84 85 inline int cost() { 86 int ans=0; 87 while(spfa()) 88 ans+=change(); 89 return ans; 90 } 91 92 inline int hhh() { 93 read(n);read(m); 94 src=0;decc=2*n+1; 95 memset(head,-1,sizeof head); 96 for(int i=1;i<=n;i++) { 97 read(a); 98 add_edge(src,i+n,1,a); 99 add_edge(src,i,1,0); 100 add_edge(i+n,decc,1,0); 101 } 102 for(int i=1;i<=m;i++) { 103 read(a);read(b);read(c); 104 if(a>b) swap(a,b); 105 add_edge(a,b+n,1,c); 106 } 107 printf("%d ",cost()); 108 return 0; 109 } 110 111 int sb=hhh(); 112 int main() {;}