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;}

?

?

?