个人感觉这个题不错，是传说中的DP+MST。
用f[i]表示到第i天的最小价值，那么就有转移
从第j天改变方案持续到第i天，那么就是f[j-1]+cos*(j-i+1)*v+k。
其中的cos用kruscal求得。你用prim会挂啊有木有！
还有一个应该注意的是如何处理这个哪条道路有灾害。
一开始是想每条边开一个st,ed。结果发现是不行的因为每条道路受灾的时间不一定是连续的。比如
1 2 3 4
1 2 7 8
这种数据。那么只能开一个布尔数组h[i,t]用来表示i这条边在t时间有木有灾难，就可以了。
View Code type zj=record lef,rig,cos:longint;end;var h:array[1..20000,0..50] of boolean; e:array[1..20000] of zj; n,m,v,t,k:longint; c:array[1..20000] of boolean; f:array[0..50] of longint; a:array[1..500] of longint;function min(a,b:longint):longint;beginif a>b then exit(b) else exit(a);end;function find(x:longint):longint;beginif a[x]=0 then exit(x); find:=find(a[x]); a[x]:=find;end;procedure swap(var a,b:longint);var tmp:longint;begin tmp:=a; a:=b; b:=tmp;end;procedure qsort(l,r:longint);var i,j,m:longint; t:zj;begin i:=l; j:=r; m:=e[(l+r)shr 1].cos;repeatwhile e[i].cos<m do inc(i);while e[j].cos>m do dec(j);if i<=j then begin t:=e[i]; e[i]:=e[j]; e[j]:=t; inc(i); dec(j);end;until i>j;if i<r then qsort(i,r);if l<j then qsort(l,j);end;procedure init;var p,j,tt,x,y,z,q,i:longint;begin readln(n,m,t,v,k);for i:=1 to m dobegin readln(e[i].lef,e[i].rig,e[i].cos);if e[i].lef>e[i].rig then swap(e[i].lef,e[i].rig);end; qsort(1,m); readln(p); fillchar(h,sizeof(h),true);for i:=1 to p dobegin readln(x,y,z,q);if z>q then swap(z,q);for j:=1 to m doif ((e[j].lef=x) and (e[j].rig=y)) or ((e[j].rig=x) and (e[j].lef=y)) then beginfor tt:=z to q do h[j,tt]:=false;end;end;end;function kruscal(l,r:longint):longint;var tot,ans,i,j,p,q:longint;begin fillchar(c,sizeof(c),true);for i:=1 to m do beginfor j:=l to r doif not h[i,j] then begin c[i]:=false; break;end;end; fillchar(a,sizeof(a),0); tot:=0; ans:=0;for i:=1 to m doif c[i] then begin p:=find(e[i].lef); q:=find(e[i].rig);if p<>q then begin a[p]:=q; ans:=ans+e[i].cos; tot:=tot+1;end;if tot=n-1 then exit(ans);end; exit(maxlongint shr 2);end;procedure dp;var i,j:longint;begin filldword(f,sizeof(f) shr 2, maxlongint shr 2); f[0]:=0;for i:=1 to t dofor j:=1 to i do f[i]:=min(f[i],f[j-1]+kruscal(j,i)*(i-j+1)*v+k); writeln(f[t]);end;begin init; dp;end.
转载于:https://www.cnblogs.com/zjerly/archive/2011/11/05/2236823.html
