题目描述
魅力之都是一个有N个路口，M条双向道路连接的城市。警察叔叔绘制了一张特殊的地图，在地图上只保留了N-1条道路，我们称这些道路为【特殊道路】，要保证任意两个路口间有且仅有一条路径，且满足所有保留的道路长度之和最小。
现在要在其中一个连接有多条【特殊道路】的路口设立【根据地】，去掉【根据地】所在路口后，就会出现某些路口间无法通过【特殊道路】相互连通的情况，我们认为这时仍然能够通过【特殊道路】连通的路口属于同一个【区域】。警察叔叔希望最后每个【区域】的【特殊道路】总长尽可能平均。警察叔叔找到了hzwer，但是hzwer是个无向图和有向图都无法区分的蒟蒻，请你帮他计算出应该选择哪一个路口作为【根据地】。
(尽可能平均即权值最小，设每一块【区域】的路线总长为Length[i]（包括连接【根据地】与该【区域】的边），平均路线长度为Avg=SUM{Length[i]}/区域数，权值d=∑ (Length[i]-Avg)^2
输入格式
第1行：2个正整数N,M
第2..M+1行：每行2个整数u,v和1个实数len，表示u,v之间存在长度为len的边
输出格式
第1行：1个整数，最后选择的路口编号（存在多个可选路口时选择编号小的）
样例数据 1
输入
3 3
3 1 5
3 2 4
1 2 3
输出
2
样例数据 2
输入
3 3
2 1 825.7291
3 2 397.4120
1 3 633.1370
输出
3
备注
对于60%的数据：3 ≤ N ≤ 2,000，N-1 ≤ M ≤ 50,000
对于100%的数据：3 ≤ N ≤ 40,000，N-1 ≤ M ≤ 200,000
对于100%的数据：0 < len ≤ 100,000,000
保证不存在相同距离的线路，两个路口间可能出现多条路径，且任意点对间至少存在一条路径
题解
话说第一步是最小生成树没人不知道。n挺小的，dfs求出树上一些信息，枚举每个点即可。
考试时逗了，rest忘清零了……
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<cmath>
#include<algorithm>
#define ll long long
#define MAXM 200002
#define MAXN 40002
using namespace std;
int n,m,f[MAXN];
struct bian{int x,y; double v;} E[MAXM];
double totlen;
int zz,head[MAXN],fa[MAXN],con[MAXN],ans;
struct tree{int to,nx; double v;} e[MAXM*2];
double sum[MAXN],mind,pjlen,d,rest;
//------------------------------------------------------------------------------
bool kp(const bian &i,const bian &j) {return i.v<j.v;}
void init()
{
scanf("%d%d",&n,&m);
int i,x,y; double z;
for(i=1;i<=m;i++)
scanf("%d%d%lf",&E[i].x,&E[i].y,&E[i].v);
sort(E+1,E+m+1,kp);
}
void insert(int x,int y,double z)
{
zz++; e[zz].to=y; e[zz].v=z; e[zz].nx=head[x]; head[x]=zz;
zz++; e[zz].to=x; e[zz].v=z; e[zz].nx=head[y]; head[y]=zz;
}
int find(int x)
{
if(f[x]!=x) f[x]=find(f[x]);
return f[x];
}
void klskl()
{
int i,r1,r2;
for(i=1;i<=n;i++) f[i]=i;
for(i=1;i<=m;i++)
{r1=find(E[i].x),r2=find(E[i].y);
if(r1!=r2)
{f[r2]=r1; totlen+=E[i].v;
insert(E[i].x,E[i].y,E[i].v);
}
}
}
//------------------------------------------------------------------------------
void dfs(int x)
{
int i,p;
con[x]=1;
if(x==1) con[x]--;
for(i=head[x];i;i=e[i].nx)
{p=e[i].to;
if(p==fa[x]) continue;
sum[p]+=e[i].v; con[x]++;
fa[p]=x; dfs(p);
sum[x]+=sum[p];
}
}
double sqr(double x) {return x*x;}
void work()
{
int i,j,p;
mind=1e20;
for(i=1;i<=n;i++)
{if(con[i]<=1) continue;
d=0; pjlen=totlen/con[i]; rest=0;
for(j=head[i];j;j=e[j].nx)
{p=e[j].to;
if(p==fa[i]) continue;
d+=sqr(sum[p]-pjlen);
rest+=sum[p];
}
rest=totlen-rest;
d+=sqr(rest-pjlen);
if(d<mind)
{mind=d; ans=i;}
}
printf("%d\n",ans);
}
int main()
{
init(); klskl();
dfs(1); work();
return 0;
}