題意：
????? 讓你求一顆生成樹(shù)，使得最長(zhǎng)邊和最短邊長(zhǎng)度差值最小。

思路：
???? 額！！！感覺(jué)這個(gè)思路會(huì)超時(shí)，但是ac了，暫時(shí)沒(méi)什么別的好思路，那么就先說(shuō)下這個(gè)思路，大牛要是有好的思路希望能在下面留言，相互學(xué)習(xí)，我的方法是先把所有的邊都按長(zhǎng)度排序，然后枚舉沒(méi)一顆生成樹(shù)，這樣枚舉能得到正確答案的原因是，如果是求最小的差值，那么最終的答案一定是在sort之后的連續(xù)的以段，我們只要枚舉每一段就行了，但是這樣的時(shí)間復(fù)雜度是O(M^2)的，如果碰到奇葩數(shù)據(jù)估計(jì)一組可能跑到將近1s這樣就T了，呵呵。

?

#include<stdio.h>
#include<string.h>
#include<algorithm>

#define N 110

using namespace std;

typedef struct
{
?? int a ,b ,c;
}EDGE;

EDGE edge[N*N/2];
int mer[N];

int finds(int x)
{
??? return x == mer[x] ? x : mer[x] = finds(mer[x]);
}

bool camp(EDGE a ,EDGE b)
{
???? return a.c < b.c;
}

int main ()
{
??? int n ,m ,i ,j ,Ans;
??? while(~scanf("%d %d" ,&n ,&m) && n + m)
??? {
??????? Ans = -1;????????????
??????? for(i = 1 ;i <= m ;i ++)
??????? scanf("%d %d %d" ,&edge[i].a ,&edge[i].b ,&edge[i].c);
??????? sort(edge + 1 ,edge + m + 1 ,camp);
??????? for(i = 1 ;i <= m ;i ++)
??????? {
??????????? for(j = 1 ;j <= n ;j ++)
??????????? mer[j] = j;
??????????? int sss = 0;?
??????????? for(j = i ;j <= m ;j ++)?
??????????? {
?????????????? int xx = finds(edge[j].a);
?????????????? int yy = finds(edge[j].b);
?????????????? if(xx != yy) sss++ ,mer[xx] = yy;
?????????????? if(sss == n - 1)
?????????????? {
????????????????? if(Ans == -1 || Ans > edge[j].c - edge[i].c)
????????????????? Ans = edge[j].c - edge[i].c;
????????????????? break;
?????????????? }
??????????? }
??????? }
??????? printf("%d\n" ,Ans);
??? }
??? return 0;
}??

?

?

?

總結(jié)

以上是生活随笔為你收集整理的Poj 3522 最长边与最短边差值最小的生成树的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。