首页 > 代码库 > HDU 4756 Install Air Conditioning
HDU 4756 Install Air Conditioning
Install Air Conditioning
Time Limit: 2000ms
Memory Limit: 65535KB
This problem will be judged on HDU. Original ID: 475664-bit integer IO format: %I64d Java class name: Main
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?
Input
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.
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.
Output
For each case, output the cost, correct to two decimal places.
Sample Input
24 20 01 12 03 14 30 01 11 00 1
Sample Output
9.669.00
Source
2013 ACM/ICPC Asia Regional Nanjing Online
解题：MST+树形dp,求树形dp比较坑爹啊，看解题报告，想了半个上午才明白。。。。。。。
树形dp是为了求生成树上每条边的最小替代边。
然后求替换后，所能达到的最大值。。。。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <algorithm> 6 #include <climits> 7 #include <vector> 8 #include <queue> 9 #include <cstdlib>10 #include <string>11 #include <set>12 #include <stack>13 #define LL long long14 #define pii pair<int,int>15 #define INF 0x3f3f3f3f16 using namespace std;17 const int maxn = 1010;18 double g[maxn][maxn],d[maxn],px[maxn],py[maxn],dp[maxn][maxn];19 int p[maxn],n,m;20 vector<int>e[maxn];21 bool used[maxn][maxn];22 double getDis(int i,int j) {23 double tmp = (px[i] - px[j])*(px[i] - px[j]);24 tmp += (py[i] - py[j])*(py[i] - py[j]);25 return sqrt(tmp);26 }27 double prim() {28 bool vis[maxn] = {false};29 for(int i = 1; i <= n; ++i) {30 d[i] = INF;31 p[i] = -1;32 }33 d[1] = 0;34 double MST = 0;35 while(true) {36 double minVal = INF;37 int idx = -1;38 for(int i = 1; i <= n; ++i)39 if(!vis[i] && minVal > d[i]) minVal = d[idx = i];40 if(idx == -1 || minVal >= INF) break;41 if(p[idx] > -1) {42 e[idx].push_back(p[idx]);43 e[p[idx]].push_back(idx);44 used[idx][p[idx]] = used[p[idx]][idx] = true;45 }46 vis[idx] = true;47 MST += minVal;48 for(int i = 1; i <= n; ++i)49 if(!vis[i] && d[i] > g[idx][i]) {50 d[i] = g[idx][i];51 p[i] = idx;52 }53 }54 return MST;55 }56 double dfs(int cur,int u,int fa){57 double minV = INF;58 for(int i = e[u].size()-1; i >= 0; --i){59 if(e[u][i] == fa) continue;60 double tmp = dfs(cur,e[u][i],u);61 minV = min(tmp,minV);62 dp[u][e[u][i]] = dp[e[u][i]][u] = min(tmp,dp[u][e[u][i]]);63 }64 if(cur != fa) minV = min(minV,g[cur][u]);65 return minV;66 }67 int main() {68 int cs;69 scanf("%d",&cs);70 while(cs--){71 scanf("%d %d",&n,&m);72 for(int i = 0; i <= n; ++i) e[i].clear();73 for(int i = 1; i <= n; ++i)74 scanf("%lf %lf",px+i,py+i);75 for(int i = 1; i <= n; ++i){76 for(int j = 1; j <= n; ++j){77 if(i == j) g[i][j] = 0;78 else g[i][j] = getDis(i,j);79 dp[i][j] = INF;80 }81 }82 double MST = prim(),ans = MST;83 for(int i = 1; i <= n; ++i) dfs(i,i,-1);84 for(int i = 2; i <= n; ++i){85 for(int j = e[i].size()-1; j >= 0; --j){86 if(e[i][j] == 1) continue;87 ans = max(ans,MST - g[i][e[i][j]] + dp[i][e[i][j]]);88 }89 }90 printf("%.2f\n",ans*m);91 }92 return 0;93 }
HDU 4756 Install Air Conditioning
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。