2015
09-17

# Install Air Conditioning

NJUST carries on the tradition of HaJunGong. NJUST, who keeps up the ”people-oriented, harmonious development” of the educational philosophy and develops the ”unity, dedication, truth-seeking, innovation” school motto, has now become an engineering-based, multidisciplinary university.

As we all know, Nanjing is one of the four hottest cities in China. Students in NJUST find it hard to fall asleep during hot summer every year. They will never, however, suffer from that hot this year, which makes them really excited. NJUST’s 60th birthday is approaching, in the meantime, 50 million is spent to install air conditioning among students dormitories. Due to NJUST’s long history, the old circuits are not capable to carry heavy load, so it is necessary to set new high-load wires. To reduce cost, every wire between two dormitory is considered a segment. Now, known about all the location of dormitories and a power plant, and the cost of high-load wire per meter, Tom200 wants to know in advance, under the premise of all dormitories being able to supply electricity, the minimum cost be spent on high-load wires. And this is the minimum strategy. But Tom200 is informed that there are so many wires between two specific dormitories that we cannot set a new high-load wire between these two, otherwise it may have potential risks. The problem is that Tom200 doesn’t know exactly which two dormitories until the setting process is started. So according to the minimum strategy described above, how much cost at most you’ll spend?

The first line of the input contains a single integer T(T ≤ 100), the number of test cases.
For each case, the first line contains two integers n(3 ≤ n ≤ 1000), k(1 ≤ k ≤ 100). n represents n-1 dormitories and one power plant, k represents the cost of high-load wire per meter. n lines followed contains two integers x, y(0 ≤ x, y ≤ 10000000), representing the location of dormitory or power plant. Assume no two locations are the same, and no three locations are on a straight line. The first one is always the location of the power plant.

The first line of the input contains a single integer T(T ≤ 100), the number of test cases.
For each case, the first line contains two integers n(3 ≤ n ≤ 1000), k(1 ≤ k ≤ 100). n represents n-1 dormitories and one power plant, k represents the cost of high-load wire per meter. n lines followed contains two integers x, y(0 ≤ x, y ≤ 10000000), representing the location of dormitory or power plant. Assume no two locations are the same, and no three locations are on a straight line. The first one is always the location of the power plant.

2

4 2
0 0
1 1
2 0
3 1

4 3
0 0
1 1
1 0
0 1

9.66
9.00

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#include<vector>
using namespace std;
#define INF 2000000000
#define N 1005
double sum;
double dis[N][N];
double dp[N][N];
bool vis[N][N];
bool flag[N];
double lowcost[N];
int pre[N];
struct node
{
int x,y;
};
vector<int> tree[N];
int n,m,num;
struct point{double x,y;}p[1005];
inline double g_dis(point &A,point &B)
{
return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));
}
void prim()
{
sum=0;
int i,j;
memset(flag,false,sizeof(flag));
for(i=1;i<=n;i++)
{
lowcost[i]=dis[1][i];
pre[i]=1;
}
flag[1]=true;
for(i=1;i<n;i++)
{
double mins=INF;
int v;
for(j=1;j<=n;j++)
{
if(flag[j] == false && lowcost[j] < mins)
{
mins=lowcost[j];
v=j;
}
}
sum+=mins;
vis[pre[v]][v] = vis[v][pre[v]] = true;
tree[v].push_back(pre[v]);
tree[pre[v]].push_back(v);
flag[v] = true;
for(j=1;j<=n;j++)
{
if(flag[j] == false && lowcost[j] > dis[v][j])
{
lowcost[j] = dis[v][j];
pre[j] = v;
}
}
}
}
double dfs(int root,int now,int fa=-1)
{
double ret = INF;
for(int i = 0;i<tree[now].size();i++)
{
int to=tree[now][i];
if(to!=fa){
double tmp = dfs(root,to,now);
ret=min(tmp,ret);
dp[now][to] = dp[to][now] = min(tmp,dp[now][to]);
}
}
if(root!=fa)
ret=min(ret,dis[root][now]);
return ret;
}
int main()
{
int cas,k;
double x,y;
int i,j;
scanf("%d",&cas);
while(cas--)
{
scanf("%d%d",&n,&k);
for(i=1;i<=n;i++)
{
tree[i].clear();
scanf("%lf%lf",&x,&y);
p[i].x=x;p[i].y=y;
tree[i].clear();
}
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
vis[i][j]=false;
if(i==j) dis[i][j]=0;
else dis[i][j]=g_dis(p[i],p[j]);
dp[i][j]=INF;
}
}
prim();
double ans=sum;
for(i=1;i<=n;i++) dfs(i,i);
for(i=2;i<=n;i++)
{
for(j=2;j<i;j++)
{
if(vis[i][j])
{
ans=max(ans,sum-dis[i][j]+dp[i][j]);
}
}
}
printf("%.2lf\n",ans*k);
}
return 0;
}


1. 羅拉A萌 :路飛在船上跟火雞打電話時就說了要把火雞打飛了。如果比賽能繼續進行的話，D組過後，路飛就要和腦殘粉杠上了看了下原话 路飞当时说的是 如果你再做出伤天害理的事情 我就把你打飞。。。

2. 哈哈哈，不要了不要了，反正小金人也不是我的，哈哈哈，无所谓了，真的，哈哈哈哈，无所谓了，什么小金人不小金人，都不是我的，哈哈哈，无所谓了，哈哈哈

3. 文化决定制度是对的。所以现在许多人发表文章批评体制，没有问题？但是，没有人敢发表文章批评玛劣和某某主义和思想？为什么？因为思想文化是制度存在的理论基础和土壤

4. 红白鼯鼠（学名：Petaurista alborufus）是一种啮齿动物，体形很像松鼠，体长35-60厘米，体重2000克。头短而圆，眼睛很大，眼圈赤栗色，瞳孔特别大，可以感受微弱光线，适宜于在地洞黑暗的世界里生活。身体背面体毛为红色，面部和身体腹面为白