「CODEVS1403」新三国争霸
题目描述 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<=300，M<=5000 ，T<=50；
输入描述 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，T1，T2。表示X到Y的这条路，在T1到T2这几天都会受灾害。
输出描述 Output Description
T天在道路的防守上花费最少的军粮。
样例输入 Sample Input
3 3 5 10 30
1 2 1
2 3 2
1 3 4
1
1 3 2 5
样例输出 Sample Output
180
数据范围及提示 Data Size & Hint
各个测试点1s
题解
本题与bzoj1003类似
最小生成树+dp
最小生成树求w[i][j]即第i天到第j天不改变方案的最小消耗
注意输入中有可能出现y<x,要注意判断
然后dp
|
1 2 3 4 5 6 |
for(int i=1;i<=t;i++) { f[i]=v*w[1][i]*i+k; for(int j=1;j<=i;j++)if(w[j+1][i]!=INF) f[i]=min(f[i],f[j]+k+w[j+1][i]*v*(i-j)); } |
基本和那一题差不多。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 |
#include<iostream> #include<cstdio> #include<algorithm> #define INF 0x7fffffff using namespace std; struct data{ int x,y,v; }e[5001]; inline bool cmp(data a,data b){return a.v<b.v;} bool cr[51][301][301]; int n,m,t,v,k,p,father[301],w[51][51],f[51]; int find(int x){return x==father[x]?x:father[x]=find(father[x]);} bool pd(int a,int b,int x,int y) { for(int i=a;i<=b;i++) if(cr[i][x][y])return 0; return 1; } int krus(int a,int b) { int t=0; for(int i=1;i<=n;i++)father[i]=i; for(int i=1;i<=m;i++) { int x=e[i].x,y=e[i].y; if(pd(a,b,x,y)&&find(x)!=find(y)) { father[find(x)]=find(y); t+=e[i].v; } } for(int i=1;i<=n;i++)if(find(i)!=find(1))return INF; return t; } void dp() { for(int i=1;i<=t;i++) { f[i]=v*w[1][i]*i+k; for(int j=1;j<=i;j++)if(w[j+1][i]!=INF) f[i]=min(f[i],f[j]+k+w[j+1][i]*v*(i-j)); } } int main() { scanf("%d%d%d%d%d",&n,&m,&t,&v,&k); for(int i=1;i<=m;i++) { scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].v); if(e[i].x>e[i].y)swap(e[i].x,e[i].y); } sort(e+1,e+m+1,cmp); scanf("%d",&p); for(int i=1;i<=p;i++) { int x,y,t1,t2; scanf("%d%d%d%d",&x,&y,&t1,&t2); if(x>y)swap(x,y); if(t1>t2)swap(t1,t2); for(int j=t1;j<=t2;j++)cr[j][x][y]=1; } for(int i=1;i<=t;i++) for(int j=i;j<=t;j++) w[i][j]=krus(i,j); dp(); printf("%d",f[t]); return 0; } |
判断过程可以枚举，也可以用前缀和。。不过由于改用int数组空间花费较大
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 |
#include<iostream> #include<cstdio> #include<algorithm> #define INF 0x7fffffff using namespace std; struct data{ int x,y,v; }e[5001]; inline bool cmp(data a,data b){return a.v<b.v;} int cr[51][301][301],n,m,t,v,k,p,father[301],w[51][51],f[51]; int find(int x){return x==father[x]?x:father[x]=find(father[x]);} int krus(int a,int b) { int t=0; for(int i=1;i<=n;i++)father[i]=i; for(int i=1;i<=m;i++) { int x=e[i].x,y=e[i].y; if(cr[b][x][y]-cr[a-1][x][y]==0&&find(x)!=find(y)) { father[find(x)]=find(y); t+=e[i].v; } } for(int i=1;i<=n;i++)if(find(i)!=find(1))return INF; return t; } void dp() { for(int i=1;i<=t;i++) { f[i]=v*w[1][i]*i+k; for(int j=1;j<=i;j++)if(w[j+1][i]!=INF) f[i]=min(f[i],f[j]+k+w[j+1][i]*v*(i-j)); } } int main() { scanf("%d%d%d%d%d",&n,&m,&t,&v,&k); for(int i=1;i<=m;i++) { scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].v); if(e[i].x>e[i].y)swap(e[i].x,e[i].y); } sort(e+1,e+m+1,cmp); scanf("%d",&p); for(int i=1;i<=p;i++) { int x,y,t1,t2; scanf("%d%d%d%d",&x,&y,&t1,&t2); if(x>y)swap(x,y); if(t1>t2)swap(t1,t2); for(int j=t1;j<=t2;j++)cr[j][x][y]=1; } for(int l=1;l<=t;l++) for(int i=1;i<=n;i++) for(int j=i;j<=n;j++) cr[l][i][j]+=cr[l-1][i][j]; for(int i=1;i<=t;i++) for(int j=i;j<=t;j++) w[i][j]=krus(i,j); dp(); printf("%d",f[t]); return 0; } |
OI 课件=>
