首页 > ACM题库 > HDU-杭电 > HDU 4126-Genghis Khan the Conqueror-最小生成树-[解题报告]HOJ
2015
04-16

HDU 4126-Genghis Khan the Conqueror-最小生成树-[解题报告]HOJ

Genghis Khan the Conqueror

问题描述 :

Genghis Khan(成吉思汗)(1162-1227), also known by his birth name Temujin(铁木真) and temple name Taizu(元太祖), was the founder of the Mongol Empire and the greatest conqueror in Chinese history. After uniting many of the nomadic tribes on the Mongolian steppe, Genghis Khan founded a strong cavalry equipped by irony discipline, sabers and powder, and he became to the most fearsome conqueror in the history. He stretched the empire that resulted in the conquest of most of Eurasia. The following figure (origin: Wikipedia) shows the territory of Mongol Empire at that time.
Moles

Our story is about Jebei Noyan(哲别), who was one of the most famous generals in Genghis Khan’s cavalry. Once his led the advance troop to invade a country named Pushtuar. The knights rolled up all the cities in Pushtuar rapidly. As Jebei Noyan’s advance troop did not have enough soldiers, the conquest was temporary and vulnerable and he was waiting for the Genghis Khan’s reinforce. At the meantime, Jebei Noyan needed to set up many guarders on the road of the country in order to guarantee that his troop in each city can send and receive messages safely and promptly through those roads.

There were N cities in Pushtuar and there were bidirectional roads connecting cities. If Jebei set up guarders on a road, it was totally safe to deliver messages between the two cities connected by the road. However setting up guarders on different road took different cost based on the distance, road condition and the residual armed power nearby. Jebei had known the cost of setting up guarders on each road. He wanted to guarantee that each two cities can safely deliver messages either directly or indirectly and the total cost was minimal.

Things will always get a little bit harder. As a sophisticated general, Jebei predicted that there would be one uprising happening in the country sooner or later which might increase the cost (setting up guarders) on exactly ONE road. Nevertheless he did not know which road would be affected, but only got the information of some suspicious road cost changes. We assumed that the probability of each suspicious case was the same. Since that after the uprising happened, the plan of guarder setting should be rearranged to achieve the minimal cost, Jebei Noyan wanted to know the new expected minimal total cost immediately based on current information.

输入:

There are no more than 20 test cases in the input.
For each test case, the first line contains two integers N and M (1<=N<=3000, 0<=M<=N×N), demonstrating the number of cities and roads in Pushtuar. Cities are numbered from 0 to N-1. In the each of the following M lines, there are three integers xi, yi and ci(ci<=107), showing that there is a bidirectional road between xi and yi, while the cost of setting up guarders on this road is ci. We guarantee that the graph is connected. The total cost of the graph is less or equal to 109.

The next line contains an integer Q (1<=Q<=10000) representing the number of suspicious road cost changes. In the following Q lines, each line contains three integers Xi, Yi and Ci showing that the cost of road (Xi, Yi) may change to Ci (Ci<=107). We guarantee that the road always exists and Ci is larger than the original cost (we guarantee that there is at most one road connecting two cities directly). Please note that the probability of each suspicious road cost change is the same.

输出:

There are no more than 20 test cases in the input.
For each test case, the first line contains two integers N and M (1<=N<=3000, 0<=M<=N×N), demonstrating the number of cities and roads in Pushtuar. Cities are numbered from 0 to N-1. In the each of the following M lines, there are three integers xi, yi and ci(ci<=107), showing that there is a bidirectional road between xi and yi, while the cost of setting up guarders on this road is ci. We guarantee that the graph is connected. The total cost of the graph is less or equal to 109.

The next line contains an integer Q (1<=Q<=10000) representing the number of suspicious road cost changes. In the following Q lines, each line contains three integers Xi, Yi and Ci showing that the cost of road (Xi, Yi) may change to Ci (Ci<=107). We guarantee that the road always exists and Ci is larger than the original cost (we guarantee that there is at most one road connecting two cities directly). Please note that the probability of each suspicious road cost change is the same.

样例输入:

3 3
0 1 3
0 2 2
1 2 5
3
0 2 3
1 2 6
0 1 6
0 0

样例输出:

6.0000
Hint
The initial minimal cost is 5 by connecting city 0 to 1 and city 0 to 2. In the first suspicious case, the minimal total cost is increased to 6; the second case remains 5; the third case is increased to 7. As the result, the expected cost is (5+6+7)/3 = 6.

      http://acm.hdu.edu.cn/showproblem.php?pid=4126

       题目的大意给你一张连通图,共有Q次更改,每次在原图的基础上,增加一条边的权值,求每次更改后最小生成树的权的总和sum,并输出sum/Q;

       思路:对原图做一次pim(),求出最小生树,如果修改的权值不是最小生成树的边,那边最小生成树不变。否则,假设修改的边是(a,b)并把(a,b)的权值修改为c,那个我们把 (a,b)边从最小生成树中去掉,就形成两棵树T1,T2,那么最小生成树就可以由T1,T2加上连接 T1 和T2的权值最小的边。

       证明:如果修改的值不在最小生成树上,由于修改是增加权值,对原图求最小生成树,增加的值不会影响结果,所以最小生成树不变。如果,修改的值在最小生成树上,那么把修改的边去掉形成两棵树T1,T2,我们可以肯定有一棵最小生成树包含T1,T2的所有边。首先,我们证明一个最生成树的性质。我们假设(u,v)是最小生成树上的边,我们在树小生成树上任意加边,使得形成包含 (u,v)边的环,可以肯定环中必有一条边(u’,v’),使
w(u’,v’) >=w(u,v) ,否则,我们可以去掉(u,v),么新的生成树的权值就比现在的最小生成树的权值小,与其是最小生成树的条件矛盾。我们回到这个题目,我们不妨设最后的最小生成树,不包含T1上的任意边(u,v),那么把(u,v)边加到最小生成树上,则可以形成一个环,因为(u,v)在原图的最小生成树上,我们可以肯定可以找到一条边(u’,v’)使得w(u,v) <= w(u’,v’),把(u,v)代替(u’,v’)可以得到一个和原本最小生成树值相同的生成树,即可以得到一个包含边(u,v)的最小生成树。因此,必定有一棵最小生成树包含T1,T2上的全部边,那么我们只要把T1,T2用最小代价连接起来就可以得到最小生树了。

      我们回到实际的算法,题目的图共有N(1<=N<=3000)个点, Q (1<=Q<=10000)次修改。进行一个prim()求最小生成树要O(n^2)在约是3000*3000 的复杂度,关键是怎么求去掉最小生成树上边,求连接两棵树的最小代价。这一步我原本是想要用堆写,可以我发现写完后各种bug,无奈看了网上的题解(看这篇题解)说用dp可以解决。我们用dp[i][j],表示从j及j的子树到i的最小代价,则dp[i][j]
= min(dp[i][k],k是j的直接子结点),由于要满足后效性,我们可以直接在树上做dp,也可以先对树进行求前序遍历 ,根据遍历 的次序进行dp。后一种方法,听起来比较复杂,但实际操作中两种没差多少,且在很多题目中,用后一种进行dp,可以比较灵活地优化。

   下面是源代码:



#include <stdio.h>
#include <stdlib.h>
#include <string.h>

const int maxn = 3300;
const int maxm = maxn*maxn;
const int INF = 0x7f7f7f7f;

int n, m, mst, mark;

int cost[maxn];
//node's father;
int father[maxn];
int *fa = father;
//The son of each node
int son[maxn];
//Every node's ID
int dfn[maxn]; 
//the order;
int ndfs[maxn];
int dp[maxn][maxn];

int edge_sum;
int head[maxn];
int tree_head[maxn];
typedef struct Edge{
	int v;
	int w;
	int next;
}Edge;

Edge edge[maxm];
Edge tree[maxn];

void init(){
	mark = 0;
	edge_sum = 0;
	memset(head,-1,sizeof(head));
	memset(father,-1,sizeof(father));
	memset(tree_head,-1,sizeof(tree_head));
}

void getData(){
	int a, b, c;
	for(int i = 0; i < m; i++){	
		scanf("%d%d%d",&a,&b,&c);
		edge[edge_sum].v = b;
		edge[edge_sum].w = c;
		edge[edge_sum].next = head[a];
		head[a] = edge_sum++; 

		edge[edge_sum].v = a;
		edge[edge_sum].w = c;
		edge[edge_sum].next = head[b];
		head[b] = edge_sum++;
	}
}

int dis[maxn];
bool vist[maxn];
int closed[maxn];

void prim(){
	int i, j;			
	memset(dis,0x7f,sizeof(dis));
	memset(vist,false,sizeof(vist));

	for(i = head[0]; i != -1; i = edge[i].next){
		closed[edge[i].v] = 0;
		dis[edge[i].v] = edge[i].w;
	}

	mst = 0;
	dis[0] = INF;
	vist[0] = true;

	for(i = 0; i < n-1; i++){
		int k = 0;
		for(j = 1; j < n; j++)
			if(!vist[j] && dis[j] < dis[k])
				k = j;

		mst += dis[k];
		cost[k] = dis[k];
		vist[k] = true;

		father[k] = closed[k];
		tree[i].v = k;
		tree[i].next = tree_head[closed[k]];
		tree_head[closed[k]] = i;

		for(j = head[k]; j != -1; j = edge[j].next){
			if(vist[edge[j].v]) continue;
			if(edge[j].w > dis[edge[j].v]) continue;
			closed[edge[j].v] = k;
			dis[edge[j].v] = edge[j].w;
		}
	}
}

void dfs(int root){
	son[root] = 1;
	dfn[root] = mark;
	ndfs[mark++] = root;
	for(int i = tree_head[root];i != -1; i = tree[i].next){
		dfs(tree[i].v);
		son[root] += son[tree[i].v];
	}
}

int min(int a, int b){
	if(a < b) return a;
	else return b;
}

inline void swap(int &a, int &b){
	int c;
	c = a;
	a = b;
	b = c;
}

void work(){
	int i, j;
	memset(dp,0x7f,sizeof(dp));
	for(i = 0; i < n; i++)
		for(j = head[i]; j != -1; j = edge[j].next)
			if(fa[edge[j].v] != i && fa[i] != edge[j].v){
				dp[i][edge[j].v] = edge[j].w;
			}
	for(i = 0; i < n; i++)
		for(j = n-1; j > 0; j--)
			dp[i][fa[ndfs[j]]] = min(dp[i][fa[ndfs[j]]],dp[i][ndfs[j]]);
}

int ans[maxn];
void qurry(){
	memset(ans,-1,sizeof(ans));
	int i, j, Q, x, y, c;
	double sum = 0;
	scanf("%d",&Q);

	for(int ii = 0; ii < Q; ii++){
		scanf("%d%d%d",&x,&y,&c);
		if(father[x] == y) swap(x,y);
		if(fa[x] != y && fa[y] != x){
			sum += mst;
		}else if(father[y] == x && ans[y] != -1){
			sum += mst - cost[y] + min(ans[y],c);
		}else{
			ans[y] = INF;
			for(i = 0; i < n; i++){
				if(dfn[i] < dfn[y] || dfn[i] > dfn[y] + son[y] -1)
					ans[y] = min(ans[y],dp[i][y]);
				else
					ans[y] = min(ans[y],dp[x][i]);
			}

			sum += mst - cost[y] + min(ans[y],c);
		}
	}

	printf("%0.4lf\n",sum/Q);
}

int main(){
	while(~scanf("%d%d",&n,&m)){
		if(n == 0 && m == 0) break;
		init();
		getData();
		prim();
		dfs(0);
		work();
		qurry();
	}
	return 0;
}

转载请注明出处–nothi


参考资料

Grastyele

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/nothi/article/details/7886187