出题人真 口袋迷
很容易发现这是一道费用流的题目
很显然这个问题有两个难点：
-
保证走到某个点时之前序号的点都被走过
-
保证每个点都走
对于1，我们换个说法，一个人走到该点时经过的点的序号都小于该点----->3
只要满足了2和3，就一定满足1
现在来看3，也就是说两个点之间的最短路i，j，必须由k（k<j) 来更新
很像是floyd，事实上我们只要改一改floyd就能满足3
下面的问题就是，怎么满足2，也就是称之为有下界的网络流
这里学习了一个非常厉害的方法解决此类问题：
加无穷小边连接汇点
对于这道题，我们把除了0号点的以外点拆成两个点，之间连两条边
一条流量为1，费用为负无穷；一条流量为无穷，费用为0
什么意思呢？第二条边好理解，表示每个点都可以被经过无数次
第一条边什么意思呢？保证每个点都被走过；
因为这条边的费用为极小边，根据费用流的算法，这条边一定会被走过，等价于这个点一定会被走过；
最后计算总费用的时候我们再把负费用弄掉即可
后记：
话说，我在省选的前几天做了这道题目，说了都是泪啊；
考试的时候D2 T1同样也是有下界的网络流，比这题还简单，
这不过是边的容量下界是1,（一样的道理，在每条边的基础上加一条流为1，费用为这条边的费用-极小量即可）
我也很好的写出了处理有下界的网络流的方法；
可我偏偏脑抽的用到了邻接矩阵，这样就毫无意外的被重边卡死了T T
自作孽，不可活…………
UPD：注意这个程序虽然能过但有点问题，具体见后续
1 const inf=100000007; 2 bi=10000; 3 type node=record 4 from,point,cost,flow,next:longint; 5 end; 6 7 var edge:array[0..200010] of node; 8 q:array[0..200010] of longint; 9 a:array[0..400,0..400] of longint; 10 p,pre,d:array[0..700] of longint; 11 v:array[0..700] of boolean; 12 len,x,y,z,ans,n,m,k,i,j,w,t:longint; 13 14 procedure add(x,y,f,w:longint); 15 begin 16 inc(len); 17 edge[len].from:=x; 18 edge[len].point:=y; 19 edge[len].flow:=f; 20 edge[len].cost:=w; 21 edge[len].next:=p[x]; 22 p[x]:=len; 23 end; 24 25 function spfa:boolean; //网络流基本模板 26 var i,f,r,x,y:longint; 27 begin 28 fillchar(v,sizeof(v),false); 29 for i:=1 to t do 30 d[i]:=inf; 31 d[0]:=0; 32 f:=1; 33 r:=1; 34 q[1]:=0; 35 v[0]:=true; 36 while f<=r do 37 begin 38 x:=q[f]; 39 v[x]:=false; 40 i:=p[x]; 41 while i<>-1 do 42 begin 43 y:=edge[i].point; 44 if edge[i].flow>0 then 45 begin 46 if d[y]>d[x]+edge[i].cost then 47 begin 48 d[y]:=d[x]+edge[i].cost; 49 pre[y]:=i; 50 if not v[y] then 51 begin 52 v[y]:=true; 53 inc(r); 54 q[r]:=y; 55 end; 56 end; 57 end; 58 i:=edge[i].next; 59 end; 60 inc(f); 61 end; 62 if d[t]=inf then exit(false) else exit(true); 63 end; 64 65 procedure mincost; //费用流 66 var i,j:longint; 67 begin 68 while spfa do 69 begin 70 i:=t; 71 while i<>0 do 72 begin 73 j:=pre[i]; 74 dec(edge[j].flow); //每次只会流一个人 75 inc(edge[j xor 1].flow); 76 i:=edge[j].from; 77 end; 78 ans:=ans+d[t]; 79 end; 80 end; 81 82 begin 83 readln(n,m,w); 84 inc(n); 85 len:=-1; 86 fillchar(p,sizeof(p),255); 87 for i:=1 to n do 88 begin 89 for j:=1 to n do 90 a[i,j]:=inf; 91 a[i,i]:=0; 92 end; 93 t:=2*n+1; 94 for i:=1 to m do 95 begin 96 readln(x,y,z); 97 inc(x); //仅仅是为了方便 98 inc(y); 99 if a[x,y]>z then 100 begin 101 a[x,y]:=z; 102 a[y,x]:=z; 103 end; 104 end; 105 add(0,1,w,0); //一共有w个人，自然流量为w 106 add(1,0,0,0); 107 for i:=2 to n do 108 begin 109 add(i,i+n,1,-bi); //处理下界网络流简单快捷的方法 110 add(i+n,i,0,bi); 111 add(i+n,t,1,0); //每个人都可以停在当前点不走，流直接流出 112 add(t,n+i,0,0); 113 end; 114 for k:=1 to n do 115 begin 116 for i:=1 to n do 117 if i<>k then 118 for j:=1 to n do 119 if (i<>j) and (j<>k) then 120 a[i,j]:=min(a[i,j],a[i,k]+a[k,j]); 121 if k<>1 then 122 begin 123 add(1,k,1,a[1,k]); 124 add(k,1,0,-a[1,k]); 125 end; 126 for i:=2 to k-1 do // 边做边建图，显然这时候，i到k的最短路径一定是由编号小于k的点更新来的 127 begin 128 add(i+n,k,1,a[i,k]); //这个地方和上面流量为什么是1呢？点i到下一个点j可行最小路径只要走一次， 129 如果这条路径实际需要走多次的话，那必然有点i到点k的可行最短路径由ij可行最短路更新的来 130 于是下一次找增广路的时候，我们直接走ik之间最短路即可 131 所以这里我们把每条路径流量限制为1，这样寻找增广路的速度会更快 132 （当然像考试时拿不准还是写成inf吧 133 add(k,i+n,0,-a[i,k]); 134 end; 135 end; 136 mincost; 137 writeln(ans+(n-1)*bi); //修正ans 138 end.