HDU_4081_最小生成树+次小生成树性质

HDU 4081

  • 存坐标点然后建图
  • 为了使得总长度(除去一条特殊的道路)可能小.那么求出最短路.
  • 然后枚举图中的每一条边,A已知.

    B的求法

  1. 如果在最小生成树中就将最短路的和-此条边的长度=剩余总长度
  2. 如果此边不在最小生成树中.根据生成树的性质,这条边和最小生成树组成环,我们要减去(除去此边)之外的最长边,这样才能使其他的路总和最少(和判断是否存在次小生成树的维护过程一样)
  • 在求最小生成树的时候恰好能够维护最小生成树中每两个点之间的最长距离,所以如果枚举到了不在生成树上的边,由上面知这时组成了环,maxdist[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
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    #include <iostream>
    #include <algorithm>
    #include <string.h>
    #include <math.h>

    using namespace std;
    const int maxn = 1e3 + 5;
    const int INF = 0x3f3f3f3f;

    bool vis[maxn],use[maxn][maxn];
    double dist[maxn];
    double e[maxn][maxn], maxdist[maxn][maxn];
    int pre[maxn];
    int n, m;
    double prim() {
    	double sum = 0;
    	memset(vis, 0, sizeof vis);
    	memset(use, 0, sizeof use);
    	memset(maxdist, 0, sizeof maxdist);
    	vis[1] = 1; //点1加入到最小生成树中
    	for (int i = 1; i <= n; i++) {
    		dist[i] = e[1][i];
    		pre[i] = 1;
    	}
    	pre[1] = 0;
    	for (int i = 1; i < n; i++) {
    		double minn = 1.0*INF;
    		int point = INF;
    		for (int j = 1; j <= n; j++) {
    			if (!vis[j] && dist[j] < minn) {
    				point = j;
    				minn = dist[j];
    			}
    		}
    		vis[point] = 1;
    		sum += minn;
    		use[point][pre[point]] = use[pre[point]][point] = 1; //标记在树的点

    		for (int j = 1; j <= n; j++) { //更新每个点到树的距离
    			if (vis[j] && e[point][j] != 1.0*INF)
    				maxdist[j][point] = maxdist[point][j] = max(maxdist[j][pre[point]], dist[point]);
    			if (!vis[j] && e[point][j] < dist[j]) {
    				dist[j] = e[point][j];
    				pre[j] = point; //既然更新了路径,也更新该点指向的上一个点
    			}
    		}
    	}
    	return sum;
    }
    struct node {
    	int x, y, p;
    	node(){}
    	node(int x1,int y1,int p1) {
    		x = x1; y = y1; p = p1;
    	}
    }point[maxn];
    double getdist(node& a,node& b) {
    	return sqrt(1.0*(a.x - b.x)*(a.x - b.x) + 1.0*(a.y - b.y)*(a.y - b.y) );
    }
    int main() {
    //	freopen("a.txt","r",stdin);
    	int times; cin >> times;
    	while (times--) {
    		cin >> n; 
    		//memset(e, 0x3f, sizeof e);
    		for (int i = 0; i < maxn; i++)
    			for (int j = 0; j < maxn; j++)
    				e[i][j] = 1.0 * INF;
    		for (int i = 1; i <= n; i++) {
    			int u, v, w;
    			scanf("%d%d%d",&u,&v,&w);
    			point[i] = node(u,v,w);
    		}
    		for (int i = 1; i < n; i++)
    			for (int j = i + 1; j <= n; j++) {
    				e[i][j] = e[j][i] = getdist(point[i],point[j]);
    //				printf("e[][] = %.2lf\n",getdist(point[i],point[j]));
    			}
    		double b = prim(), a, ans = -1;
    //		printf("b=%.2lf\n",b);
    		for (int i = 1; i < n; i++)
    			for (int j = i+1; j <= n; j++) {
    				a = 1.0*point[i].p + 1.0*point[j].p;
    				if (use[i][j]) {
    //					printf("i=%d j=%d \n",i,j);
    					ans = max(ans,a/(b - e[i][j]));
    //					printf("e[][] = %.2lf\n",e[i][j]);
    				}
    				else {
    					ans = max(ans,a/(b - maxdist[i][j]));
    //					printf("maxdist[][] = %.2lf\n",maxdist[i][j]);
    				}
    			}
    		printf("%.2lf\n",ans);
    	}
    	return 0;
    }