题目描述Description
PP 特别喜欢玩即时战略类游戏，但他觉得那些游戏都有美中不足的地方。灾害总不降临道路，而只降临城市，而且道路不能被占领，没有保护粮草的真实性。于是他就研发了《新三国争霸》。
在这款游戏中，加入灾害对道路的影响（也就是一旦道路W[i，j]受到了灾害的影响，那么在一定时间内，这条路将不能通过）和道路的占领权（对于一条道路W[i，j]，至少需要K[i，j]个士兵才能守住）。 PP可真是高手，不一会，就攻下了N-1座城市，加上原来的就有N座城市了，但他忽略了一点……那就是防守同样重要，不过现在还来的及。因为才打完仗所以很多城市都需要建设，PP估算了一下，大概需要T天。他现在无暇分身进攻了，只好在这T天内好好的搞建设了。所以他秒要派士兵占领一些道路，以确保任何两个城市之间都有路（不然敌人就要分而攻之了，是很危险的）。士兵可不是白干活的，每个士兵每天都要吃掉V的军粮。因为有灾害，所以方案可能有变化（每改变一次就需要K的军粮，初始方案也需要K的军粮）。 因为游戏是PP编的，所以他知道什么时候有灾害。PP可是一个很节约的人，他希望这T天在道路的防守上花最少的军粮。\(N\leq300\)，\(M\leq5000\) ，\(T\leq50\)输入描述Input Description
第一行有5个整数\(N\)，\(M\)，\(T\)，\(V\)，\(K\)。\(N\)表示有城市数，\(M\)表示道路数，\(T\)表示需要修养的天数，\(V\)表示每个士兵每天吃掉的军粮数，\(K\)表示修改一次花掉的军粮数。
以下M行，每行3个数\(A\)，\(B\)，\(C\)。表示\(A\)与\(B\)有一条路（路是双向的）需要\(C\)个士兵才能守住。 第\(M+2\)行是一个数P，表示有\(P\)个灾害。 以下P行，每行4个数\(X\)，\(Y\)，\(T_1\)，\(T_2\)。表示X到Y的这条路，在\(T_1\)到\(T_2\)这几天都会受灾害。输出描述Output Description
\(T\)天在道路的防守上花费最少的军粮。
样例输入Sample Input
3 3 5 10 301 2 12 3 21 3 411 3 2 5
样例输出Sample Output
180
数据范围及提示Data Size & Hint
各个测试点\(1s\)
Solution
emmmm没什么好说的。
像这种，可以保持一段时间状态不变的东西基本上都可以DP。今天不知道脑子坏成了什么样子，这么裸的题目想了好半天。
然后用Kruskal预处理出来从\(i\)天到\(j\)天用同一种状态的最小代价\(w[i][j]\)。然后直接暴力转移。令\(dp[i]\)表示到第\(i\)天的最小代价。
\[dp[i]=min\{dp[j]+w[j+1][i]\times V*(i-j)+K|0\leq j<i\}\]
#include#include #include #include using namespace std;#define lowbit(x) ((x)&(-(x)))#define REP(i,a,n) for(register int i=(a);i<=(n);++i)#define PER(i,a,n) for(register int i=(a);i>=(n);--i)#define FEC(i,x) for(register int i=head[x];i;i=g[i].ne)#define dbg(...) fprintf(stderr,__VA_ARGS__)namespace io{ const int SIZE=(1<<21)+1;char ibuf[SIZE],*iS,*iT,obuf[SIZE],*oS=obuf,*oT=oS+SIZE-1,c,qu[55];int f,qr; #define gc() (iS==iT?(iT=(iS=ibuf)+fread(ibuf,1,SIZE,stdin),(iS==iT?EOF:*iS++)):*iS++) inline void flush(){fwrite(obuf,1,oS-obuf,stdout);oS=obuf;} inline void putc(char x){*oS++=x;if(oS==oT)flush();} template inline void read(I &x){for(f=1,c=gc();c<'0'||c>'9';c=gc())if(c=='-')f=-1;for(x=0;c<='9'&&c>='0';c=gc())x=x*10+(c&15);x*=f;} template inline void write(I x){if(!x)putc('0');if(x<0)putc('-'),x=-x;while(x)qu[++qr]=x%10+'0',x/=10;while(qr)putc(qu[qr--]);} struct Flusher_{~Flusher_(){flush();}}io_flusher_;}//orz laofudasuanusing io::read;using io::putc;using io::write;typedef long long ll;typedef unsigned long long ull;template inline bool SMAX(A&x,const B&y){return y>x?x=y,1:0;}template inline bool SMIN(A&x,const B&y){return y