这个题联系的时候没有做出来。最后还是lyd神犇教的。。。我还是太弱了。。
每个点拆成一个入点（右边一排）和一个出点（左边一排），源点S向每个出点连容量1费用0的边，每个入点向汇点连容量1费用0的边，如果有高速航道(x,y)，注意x<y，那么从x的出点到y的入点连容量1费用为读入权值的边。这样就能够处理所有高速航道了……
空间跳跃处理：从S向所有入点连容量1费用为定位费用的边就行了。
流过一个点对应的出点不代表经过了这个点，只有流过了这个点对应的的入点才算真正流过了这个点！
View Code
1 #include <iostream> 2 #include <algorithm> 3 #include <cstring> 4 #include <cstdio> 5 #include <cstdlib> 6 7 #define N 10000 8 #define M 1000000 9 10 using namespace std; 11 12 int head[N],next[M],to[M],pr[M],len[M]; 13 int q[M*5],dis[N],pre[N]; 14 bool vis[N]; 15 int n,m,cnt,S,T; 16 17 inline void add(int u,int v,int r,int w) 18 { 19 to[cnt]=v; len[cnt]=r; pr[cnt]=w; next[cnt]=head[u]; head[u]=cnt++; 20 to[cnt]=u; len[cnt]=0; pr[cnt]=-w; next[cnt]=head[v]; head[v]=cnt++; 21 } 22 23 inline void read() 24 { 25 memset(head,-1,sizeof head); cnt=0; 26 scanf("%d%d",&n,&m); 27 S=0; T=2*n+1; 28 for(int i=1,a;i<=n;i++) 29 { 30 scanf("%d",&a); 31 add(S,i+n,1,a); 32 } 33 for(int i=1,a,b,c;i<=m;i++) 34 { 35 scanf("%d%d%d",&a,&b,&c); 36 if(a>b) swap(a,b); 37 add(a,b+n,1,c); 38 } 39 for(int i=1;i<=n;i++) add(S,i,1,0),add(i+n,T,1,0); 40 } 41 42 inline bool spfa() 43 { 44 memset(dis,0x3f,sizeof dis); 45 memset(pre,-1,sizeof pre); 46 int h=1,t=2,sta; 47 q[1]=S; vis[S]=true; dis[S]=0; 48 while(h<t) 49 { 50 sta=q[h++]; vis[sta]=false; 51 for(int i=head[sta];~i;i=next[i]) 52 if(len[i]&&dis[to[i]]>dis[sta]+pr[i]) 53 { 54 dis[to[i]]=dis[sta]+pr[i]; 55 pre[to[i]]=i; 56 if(!vis[to[i]]) vis[to[i]]=true,q[t++]=to[i]; 57 } 58 } 59 return pre[T]!=-1; 60 } 61 62 inline void updata() 63 { 64 for(int i=pre[T];~i;i=pre[to[i^1]]) 65 { 66 len[i]-=1; len[i^1]+=1; 67 } 68 } 69 70 inline void go() 71 { 72 int ans=0; 73 while(spfa()) ans+=dis[T],updata(); 74 printf("%d\n",ans); 75 } 76 77 int main() 78 { 79 read(); 80 go(); 81 return 0; 82 }