hdu 2121 Ice_cream’s world II

本文从WordPress迁移而来, 查看全部WordPress迁移文章

无定根的最小树形图

题意：给出一个有向图，找出一个点为中心，使到中心可以去到其余所有顶点，并且花费最小。如果有多种可能，那么要使

题意很直白，就是要求一个最小树形图，但是有点不同的是，这样的最小树形图可能很多种，一种暴力的方法是枚举每个点，以这个点作为根，求一次最小树形图，计算就知道时间复杂度超出了限制。于是用一个巧妙的方法。原图的顶点从0到n-1标号，设置一个虚根为n，n和其余每个点连一条边，以n为根求一次最小树形图。

分析一下这样做有什么后果

  1. 这样新图中一定存在最小树形图，因为根都指向了所有顶点
  2. 我们知道在一个有向图中，如果有2个或更多顶点的入度为0（没有入边指向），那么这个图是不存在最小树形图的。这个新图一定存在最小树形图，怎么知道原图是否存在最小树形图呢？做法就是之前新建的边，我们将边权设置得很大，在这种很大的情况下，如果新图的最小树形图中有2条或更多的新边，说明什么，说明原图是不存在最小树形图的！为什么？一条新边<n,k>，权值INF，这种情况下都选中它，说明根本不存在其他边指向k这个顶点，如果存在的话就会选到那条权值小的边。简单来说，正是因为原图中有2个或更多的点本来没有入边，为了构成最小树形图，才被迫选择新边，而新边是后来加的，原图根本没有。

所以可以知道如果新图存在最小树形图，形状必为 n — > root —-> 其他顶点，那么root —-> 其余顶点这个部分就是原图的最小树形图，那么原图的最小树形图的权和 = 新图最小树形图权和 - 一条新边的权

解决了求得权和的问题，怎么确定根呢？在权和相同的情况下，选根最小的，怎么选呢？

回顾一下我们是怎么建立新图的，先把原图的m条边建好，然后添加新边，添加顺序是<n,0,INF>,<n,1,INF>,<n,2,INF>………<n,n-1,INF>，这个添加顺序是关键，一定从0到n-1不能反过来。添加完后一共有m+n条边。

思考最小树形图的算法，其中一个步骤就是找到每个顶点的最小入边并且记录它的前驱即指向它的那个顶点。可知原图存在最小树形图，一定存在且仅存在一个点，它的最小入边是INF，前驱就是虚根n。可知这个点就是原图的根。但是我们找这个根，不能看它的标号，因为在求解过程中不断重新建图，每个点的标号不断变化，而原来保存好的边的信息也是不断变化的

但是注意算法中的一点，边数始终不变，并且我们知道，如果找到了那个点，满足一定存在且仅存在一个点，它的最小入边是INF，前驱就是虚根n，这一定是在后面n条边里面更新的（一共有m+n条边，只有最后n条边才是新边才能有这样的更新），而恰好这最后n条边是和n个顶点一一对应的（知道为什么之前要这样保存边了吗？）

所以只需要记录下是哪条边，就能对应回去是哪个点

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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define N 1010
#define M 10010
#define ll long long 
#define cl memset

ll sum;
int n,tot,index;
struct edge{
	int u,v,next;
	ll w;
}e[M+N];
int id[N],pre[N],vis[N];
ll in[N];

ll Directed_MST(int root,int nv,int ne){
	const ll INF = sum + 10;
	ll res = 0;
	while(true){
		for(int i = 0; i < nv; i++)
			in[i] = INF;
		for(int i = 0; i < ne; i++){
			int u = e[i].u , v = e[i].v;
			if(u != v && e[i].w < in[v]){
				in[v] = e[i].w; pre[v] = u;
				if(u == root) index = i;
			}
		}
		for(int i = 0; i < nv; i++){
			if(i == root) continue;
			if(in[i] == INF) return -1;
		}

		in[root] = 0;
		cl(id,-1,sizeof(id));
		cl(vis,-1,sizeof(vis));
		int cntnode = 0;
		for(int i = 0; i < nv; i++){
			res += in[i];
			int v = i;
			while(vis[v] != i && id[v] == -1 && v != root){
				vis[v] = i; v = pre[v];
			}
			if(v != root && id[v] == -1){
				for(int u = pre[v]; u != v; u = pre[u])
					id[u] = cntnode;
				id[v] = cntnode++;
			}
		}
		if(cntnode == 0) break;
		for(int i = 0; i < nv; i++)
			if(id[i] == -1)
				id[i] = cntnode++;
		for(int i = 0; i < ne; i++){
			int temp = e[i].v;
			e[i].u = id[e[i].u];
			e[i].v = id[e[i].v];
			if(e[i].u != e[i].v)
				e[i].w -= in[temp];
		}
		nv = cntnode;
		root = id[root];
	}
	return res;
}

int main(){
	int m;
	while(scanf("%d%d",&n,&m)!=EOF){
		sum = 0; tot = 0; index = m;
		for(int i = 0; i < m; i++){
			scanf("%d%d%I64d",&e[tot].u,&e[tot].v,&e[tot].w);
			sum += e[tot++].w;
		}
		sum += 10;
		for(int i = 0; i < n ; i++){
			e[tot].u = n; e[tot].v = i; e[tot++].w = sum;
		}
		n++;
		ll res = Directed_MST(n-1,n,tot);
		if(res == -1 || res >= 2 * sum)
			puts("impossible");
		else
			printf("%I64d %d\n",res - sum,index - m);
		puts("");
	}
	return 0;
}