HDU 1875 最小生成树prim算法
生活随笔
收集整理的這篇文章主要介紹了
HDU 1875 最小生成树prim算法
小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#define MAX 0xffffffff //定義一個(gè)最小生成樹中不可能達(dá)到的值
const int qq=+; // 點(diǎn)的上限
using namespace std;
struct point{
int x,y;
}node[qq];
double lowcost[qq][qq]; // 鄰接矩陣
int vis[qq]; // 最小生成樹的點(diǎn)集合vis數(shù)組
int n;
double f(point a,point b)
{
return sqrt(pow(a.x-b.x,2.0)+pow(a.y-b.y,2.0));
}
void build()
{
double len;
for(int j,i=;i<n;++i)
for(j=i;j<n;++j){
len=f(node[i],node[j]); // 計(jì)算兩點(diǎn)之間的距離也就是點(diǎn)與點(diǎn)的權(quán)值、
if(len>=&&len<=)
lowcost[i][j]=lowcost[j][i]=(i==j)?:len;
else
lowcost[i][j]=lowcost[j][i]=MAX; // 值為MAX 意味著這兩點(diǎn)不連通、
}
}
void prim()
{
int k,t=n;
double min,tot=;
vis[]=; //初始點(diǎn)0進(jìn)入最小生成樹數(shù)組中、
while(--t){
min=MAX;
for(int i=;i<n;++i){
if(vis[i]!=&&lowcost[][i]<min){ //lowcost[0]代表當(dāng)前的最小生成樹的最小權(quán)值數(shù)組、
min=lowcost[][i]; //找到當(dāng)前最小的權(quán)值并記錄是哪一個(gè)點(diǎn)、
k=i;
}
}
if(min==MAX) break; //如果最小權(quán)值都為MAX 也就是不連通也可以跳出循環(huán)了、
vis[k]=; // 點(diǎn)k進(jìn)入最小生成樹數(shù)組、
tot+=min; //統(tǒng)計(jì)權(quán)值、
for(int i=;i<n;++i) //因?yàn)榧尤肓艘粋€(gè)點(diǎn)到最小生成樹中,所以要更新當(dāng)前的最小權(quán)值數(shù)組、
if(vis[i]!=&&lowcost[k][i]<lowcost[][i])
lowcost[][i]=lowcost[k][i];
}
if(t==) printf("%.1f\n",tot*);
else printf("oh!\n");
}
int main()
{
int t;cin >> t;
while(t--){
memset(vis,,sizeof(vis)); //清空標(biāo)記數(shù)組、
scanf("%d",&n);
for(int i=;i<n;++i)
scanf("%d%d",&node[i].x,&node[i].y);
build();
prim();
}
}
剛做這題我模型沒轉(zhuǎn)換過來,以為只要把橫坐標(biāo)按從小到大排序,橫坐標(biāo)相同就按縱坐標(biāo)從小到大排序然后然后從左到右從下道上連接各點(diǎn)就是最小生成樹、
- - 、 錯(cuò)的太離譜了,代碼就不拿出來丟臉了
題目設(shè)置的限制條件實(shí)際上就是不連通,這點(diǎn)想通了就好做了
總結(jié)
以上是生活随笔為你收集整理的HDU 1875 最小生成树prim算法的全部內(nèi)容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: README.md使用
- 下一篇: 金属转子流量计正确购买选型