MiYu原創, 轉帖請注明 : 轉載自?______________白白の屋

題目地址:
?????????http://acm.hdu.edu.cn/showproblem.php?pid=1875
題目描述:
暢通工程再續

Time?Limit:?2000/1000?MS?(Java/Others)????Memory?Limit:?32768/32768?K?(Java/Others)
Total?Submission(s):?3822????Accepted?Submission(s):?1076


Problem?Description
相信大家都聽說一個“百島湖”的地方吧，百島湖的居民生活在不同的小島中，當他們想去其他的小島時都要通過劃小船來實現。現在政府決定大力發展百島湖，發展首先要解決的問題當然是交通問題，政府決定實現百島湖的全暢通！經過考察小組RPRush對百島湖的情況充分了解后，決定在符合條件的小島間建上橋，所謂符合條件，就是2個小島之間的距離不能小于10米，也不能大于1000米。當然，為了節省資金，只要求實現任意2個小島之間有路通即可。其中橋的價格為?100元/米。
?

Input
輸入包括多組數據。輸入首先包括一個整數T(T?<=?200)，代表有T組數據。
每組數據首先是一個整數C(C?<=?100),代表小島的個數，接下來是C組坐標，代表每個小島的坐標，這些坐標都是?0?<=?x,?y?<=?1000的整數。
?

Output
每組輸入數據輸出一行，代表建橋的最小花費，結果保留一位小數。如果無法實現工程以達到全部暢通，輸出”oh!”.
?

Sample?Input
2
2
10?10
20?20
3
1?1
2?2
1000?1000
?

Sample?Output
1414.2
oh!
題目分析:
因為邊沒有直接給出, 而是給的坐標點, 所以需要先計算 每一個點到其他任意一點的距離, 并且記錄下來.? 如下 :
??????for ( int i = 1; i <= N; ++ i )
?????????? {
???????????????? for ( int j = 1; j < i; ++ j )
???????????????? {
?????????????????????? edge[n].v1 = i;
?????????????????????? edge[n].v2 = j;
?????????????????????? edge[n].len = sqrt (?0.0?+ POW (LD[i].x - LD[j].x) + POW ( LD[i].y - LD[j].y ) );?
?????????????????????? n ++;
???????????????? }
?????????? }
注意紅色部分!!? 這樣做很安全, 不加的話, G++可以通過,但在C++上會出現編譯問題, 哥悲劇了2次 CE?? T .T.

將邊記錄好以后, 就是正宗的 最小生成樹問題了.........直接KRUSKAL了. 這個我比較熟習, 呵呵.
代碼如下:
MiYu原創, 轉帖請注明 : 轉載自?______________白白の屋


#include?<iostream>
#include?<algorithm>
#include?<cmath>
#define?POW(x)?(?(x)?*?(x)?)
using?namespace?std;
typedef?struct?{
?????int?parent;
?????int?height;???
}Tset;??
typedef?struct?treeUFS{
???????public:
??????????????treeUFS(int?n?=?0):N(n+1)?{?set?=?new?Tset[N];
??????????????????????????????????????????visited?=?new?bool[N];?
??????????????????????????????????????????for?(?int?i?=?0;?i?!=?N;?++?i)?
??????????????????????????????????????????set[i].parent?=?i,set[i].height?=?1,visited[i]?=?false;?
????????????????????????????????????????}
??????????????~treeUFS(){?delete?[]?set;?};
??????????????int?find?(?int?x?){??int?r?=?x;??while?(?r?!=?set[r].parent?)?r?=?set[r].parent;
???????????????????????????????????return?r;
????????????????????????????????}
??????????????void?setVisit?(?int?x,?int?y?)?{?visited[x]?=?visited[y]?=?true;?}?
??????????????bool?getVisit?(?int?x?)?{?return?visited[x];?}
??????????????void?Merge(?int?x,int?y?){??x?=?find?(?x?);??y?=?find?(?y?);??
???????????????????????????????????????????if?(?x?==?y?)?return;
???????????????????????????????????????????if?(?set[x].height?==?set[y].height?){
????????????????????????????????????????????????set[y].parent?=?x;
????????????????????????????????????????????????set[x].height?++;
???????????????????????????????????????????}
???????????????????????????????????????????else?if?(?set[x].height?<?set[y].height?)?{
?????????????????????????????????????????????????????set[x].parent?=?y;???????
???????????????????????????????????????????????????}
???????????????????????????????????????????else{???set[y].parent?=?x;
???????????????????????????????????????????????}
????????????????????????????????????????}
??????????????int?getTreeCount?(){?int?nCount?=?0;?for?(?int?i?=?1;?i?<?N;?++?i?){
?????????????????????????????????????????????????????????if?(?find?(i)?==?i?){
??????????????????????????????????????????????????????????????nCount?++;?
?????????????????????????????????????????????????????????}
???????????????????????????????????????????????????}
???????????????????????????????????return?nCount;
?????????????????????????????????}
???????private:
??????????????Tset?*set;
??????????????bool?*visited;
??????????????int?N;?????????
}treeUFS;?
struct?island{
???????int?x,y;
}LD[105];
typedef?struct?edge{
???????int?v1,v2;
???????double?len;
}EDGE;
EDGE?edge[5050];
bool?cmp?(?EDGE?A,?EDGE?B?)
{
?????return?A.len?<?B.len;?
}
int?main?()
{
????int?T;
????scanf?(?"%d",&T?);
????while?(?T?--?)
????{
???????????int?N;
???????????scanf?(?"%d",&N?);
???????????treeUFS?UFS?(?N?);
???????????for?(?int?i?=?1;?i?<=?N;?++?i?)
???????????{
?????????????????int?x,y;
?????????????????scanf?(?"%d%d",&LD[i].x,&LD[i].y?);
???????????}?
???????????int?n?=?1;
???????????for?(?int?i?=?1;?i?<=?N;?++?i?)
???????????{
?????????????????for?(?int?j?=?1;?j?<?i;?++?j?)
?????????????????{
???????????????????????edge[n].v1?=?i;
???????????????????????edge[n].v2?=?j;
???????????????????????edge[n].len?=?sqrt?(?0.0?+?POW?(LD[i].x?-?LD[j].x)?+?POW?(?LD[i].y?-?LD[j].y?)?);?
???????????????????????n?++;
?????????????????}
???????????}
???????????double?sum?=?0.0;
???????????n?=?N?*?(?N?-?1?)?/?2;
???????????sort?(?edge?+?1,?edge?+?n?+?1?,?cmp?);
???????????for?(?int?i?=?1;?i?<=?n;?++?i?)
???????????{
?????????????????if?(?(?(?!UFS.getVisit(edge[i].v1)?||?!UFS.getVisit(edge[i].v2)?)?||?UFS.find(edge[i].v1)?!=?UFS.find(edge[i].v2)?)?&&?edge[i].len?>=10?&&?edge[i].len?<=?1000?)?
?????????????????{
????????????????????????UFS.setVisit?(?edge[i].v1,?edge[i].v2?);
????????????????????????UFS.Merge?(?edge[i].v1,?edge[i].v2?);
????????????????????????sum?+=?edge[i].len;?
?????????????????}
???????????}
???????????int?tCount?=?UFS.getTreeCount();
???????????if?(?tCount?!=?1?)
???????????{
?????????????????puts?(?"oh!"?);
?????????????????continue;?
???????????}
???????????printf?(?"%.1lf\n",sum?*?100?);
????}
????return?0;?
}

轉載于:https://www.cnblogs.com/MiYu/archive/2010/08/18/1802678.html

總結

以上是生活随笔為你收集整理的HDOJ 1875 HDU 1875 畅通工程再续 ACM 1875 IN HDU的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。