【wikioi】1403 新三国争霸（dp+kruskal）

时间：2021-01-25 06:02:23

http://wikioi.com/problem/1403/

一开始的确感觉和bzoj1003很像，不同的是这里还要求联通，求最小的边。

我们可以想到用最小生成树（为嘛我自己想不到呢。。）

我们可以设d[i][j]表示i-j天不改变方案的最小边权和（并且是可行的，如果不可行，d[i][j]=inf）

我们再设f[i]表示第i天最小费用。

有：

f[i]=min(d[1][i]*v*i+k, f[j]+k+d[j+1][i]*v*(i-j))

（ps：这题我很愚蠢的变量重用了，导致答案一直不对。。以后要注意变量名，，不要重名了）

#include <cstdio>

#include <cstring>

#include <cmath>

#include <string>

#include <iostream>

#include <algorithm>

using namespace std;

#define rep(i, n) for(int i=0; i<(n); ++i)

#define for1(i,a,n) for(int i=(a);i<=(n);++i)

#define for2(i,a,n) for(int i=(a);i<(n);++i)

#define for3(i,a,n) for(int i=(a);i>=(n);--i)

#define for4(i,a,n) for(int i=(a);i>(n);--i)

#define CC(i,a) memset(i,a,sizeof(i))

#define read(a) a=getint()

#define print(a) printf("%d", a)

#define dbg(x) cout << #x << " = " << x << endl

#define printarr(a, n, m) rep(aaa, n+1) { rep(bbb, m+1) cout << a[aaa][bbb]; cout << endl; }

inline int getint() { int r=0, k=1; char c=getchar(); for(; c<'0'||c>'9'; c=getchar()) if(c=='-') k=-1; for(; c>='0'&&c<='9'; c=getchar()) r=r*10+c-'0'; return k*r; }

inline const int max(const int &a, const int &b) { return a>b?a:b; }

inline const int min(const int &a, const int &b) { return a<b?a:b; }

const int N=310, M=5010, T=60, oo=20000000;

bool ck[T][N][N];

int p[N], n, m, t, v, k, d[T][T], f[T];

struct ED { int x, y, w; }e[M];

const int ifind(const int &x) { return x==p[x]?x:p[x]=ifind(p[x]); }

const bool check(const int &x, const int &y, const int &u, const int &v) { for1(i, x, y) if(ck[i][u][v]) return false; return true;}

const bool cmp(const ED &a, const ED &b) { return a.w<b.w; }

inline int getans(const int &x, const int &y) {

	for1(i, 1, n) p[i]=i;

	int fx, fy, ret=0;

	for1(i, 1, m) {

		fx=ifind(e[i].x); fy=ifind(e[i].y);

		if(fx!=fy && check(x, y, e[i].x, e[i].y)) {

			p[fx]=fy;

			ret+=e[i].w;

		}

	}

	for1(i, 1, n) if(ifind(i)!=ifind(1)) return oo;

	return ret;

}

int main() {

	scanf("%d%d%d%d%d", &n, &m, &t, &v, &k);

	int x, y, c, l, r;

	for1(i, 1, m) { read(x); read(y); read(c); if(x>y) swap(x, y);  e[i].x=x; e[i].y=y; e[i].w=c; }

	sort(e+1, e+1+m, cmp);

	int p=getint();

	while(p--) {

		read(x); read(y); read(l); read(r);

		if(x>y) swap(x, y); if(l>r) swap(l, r);

		for1(i, l, r) ck[i][x][y]=true;

	}

	for1(i, 1, t) for1(j, i, t) d[i][j]=getans(i, j);

	for1(i, 1, t) {

		f[i]=d[1][i]*i*v+k;

		for2(j, 1, i) if(d[j+1][i]!=oo && f[i]>(f[j]+k+d[j+1][i]*(i-j)*v))

			f[i]=f[j]+k+d[j+1][i]*(i-j)*v;

	}

	print(f[t]);

	return 0;

}

题目描述 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

相关文章