poj 3522 枚舉+kruskal
過了樣例就能AC
注意一點 0條邊特意判斷下。是否無法構成生成樹也要判斷
#include
#include
#include
using namespace std;
#define maxn 110
int parent[maxn];
int N,M;
struct edge
{
int u,v,w;
}edges[maxn*maxn];
int cmp(void const *a,void const *b)
{
return ((struct edge *)a)->w-((struct edge *)b)->w;
}
int find(int a)
{
if(parent[a]==-1)
return a;
return find(parent[a]);
}
int krusal()
{
int i,j,k,m,n;
int ans,tmp;
qsort(edges,M,sizeof(edges[0]),cmp);
ans=0x3fffffff;
if(M==0)
return -1;
for(i=0;i
