Aisa Beijing Regional Contest-2011 Problem A 解题报告

    题意：有n个(n<=1000)城市，坐标都告诉你了，并且每个城市都有人居住，现在要修路n-1条路，使得每个城市都连通。显然，这就是一颗树。当然，边的权值就是两点的距离。条件：有一条边可以不用任何花费。问这条边的两端点的总人数/(包含这条边的最小生成树的总权值-这条边的权值)最大是多少。即(Wa+Wb)/(mst-w(a,b))最大。

    解：其实这题是次小生成树的变形。首先可以想到最小生成树。但最小生成树的边集中的不一定是最大的。考虑n只有10^3，可以枚举两点再求。

    枚举的时候，判断这条边在不在MST上，若在，直接求。若不在呢？是不是类似于次小生成树了？是的。添加这条边后，就会形成环，删去环中第二大的边(分母最小)，即MST中从a到b的最大边，再求。记录最大值即可。

    复杂度=求最小生成树的复杂度+边数。可惜没去现场赛。。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
using namespace std;
const int maxv = 1010;
const int maxe = maxv*maxv;
int n;
int p[maxv];
double Max[maxv][maxv];
int pos[maxv][2],peo[maxv];

struct Edge		//原始图
{
	int from;
	int to;
	double w;
	bool flag;
}e[maxe];
int m;

struct Tree		//最小生成树
{
	int to;
	double w;
	int next;
}tree[maxv*2];
int head[maxv],num;

struct Node		//生成树的结点
{
	int seq;	//结点编号
	double max;	//从某个点到它的路径中的最大边的长度
};

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

void makeSet()
{
	for(int i = 0; i <= n; i++)
	{
		p[i] = i;
	}
}

int findSet(int x)
{
	if(x != p[x])
		p[x] = findSet(p[x]);
	return p[x];
}

void addEdge(int from, int to, double w)
{
	tree[num].to = to;
	tree[num].w = w;
	tree[num].next = head[from];
	head[from] = num++;
}

void addEdge2(int from, int to, double w)
{
    e[m].to = to;
    e[m].from = from;
    e[m].w = w;
    e[m].flag = false;
    m++;
}

double kruscal()
{
	int i;
	int x, y;
	int edgeNum = 0;
	double result = 0;
	makeSet();
    sort(e,e+m,cmp);
	for(i = 0; i < m; i++)
	{
		x = findSet(e[i].from);
		y = findSet(e[i].to);
		if(x != y)
		{
			edgeNum++;
			addEdge(e[i].from,e[i].to,e[i].w);
			addEdge(e[i].to,e[i].from,e[i].w);
			e[i].flag = true;
			p[x] = y;
			result += e[i].w;
		}
	}
	return edgeNum == n-1 ? result : -1;
}

void bfs(int p)
{
	bool used[maxv];
	memset(used,0,sizeof(used));
	queue<Node> que;
	Node now,adj;
	now.max = 0;
	now.seq = p;
	que.push(now);
	used[p] = true;
	while(!que.empty())
	{
		Node q = que.front();
		que.pop();
		for(int i = head[q.seq]; i != -1; i = tree[i].next)
		{
			adj.seq = tree[i].to;
			adj.max = tree[i].w;
			if(!used[adj.seq])
			{
				if(q.max > adj.max)
					adj.max = q.max;
				Max[p][adj.seq] = adj.max;
				used[adj.seq] = true;
				que.push(adj);
			}
		}
	}
}

double second_MST()
{
	int i;
	double mst = kruscal();
	for(i = 1; i <= n; i++)
		bfs(i);
	double ans = -1.0;
	for(i = 0; i < m; i++)
	{
	    double tmpt;
		if(!e[i].flag)
		    tmpt = (peo[e[i].from]+peo[e[i].to])*1.0/(mst-Max[e[i].from][e[i].to]);
		else
		    tmpt = (peo[e[i].from]+peo[e[i].to])*1.0/(mst-e[i].w);
        if(ans < tmpt)
            ans = tmpt;
	}
	return ans;
}

double dis(int i, int j)
{
    return sqrt((pos[i][0]-pos[j][0])*(pos[i][0]-pos[j][0])*1.0+(pos[i][1]-pos[j][1])*(pos[i][1]-pos[j][1]));
}

int main()
{
	int i,j;
	int cases;
	scanf("%d",&cases);
	while(cases--)
	{
		scanf("%d",&n);
		m = num = 0;
		memset(head,-1,sizeof(head));
		for(i = 1; i <= n; i++)
            scanf("%d %d %d",&pos[i][0],&pos[i][1],&peo[i]);
        for(i = 1; i <= n; i++)
        {
            for(j = i+1; j <= n; j++)
            {
                double t = dis(i,j);
                addEdge2(i,j,t);
            }
        }
		printf("%.2lf\n",second_MST());
	}
	return 0;
}