http://acm.hdu.edu.cn/showproblem.php?pid=1372
以前真二,模板题
OJ真奇怪,有时能A有时W,
#include#include #include #include using namespace std;struct node{ int x,y,z;}q[100*101/2+1];int m,n;int sum=0;int bin[101];int cmp(const void *a,const void *b){ return (*(struct node *)a).z-(*(struct node *)b).z;}int findx(int x){ int r=x; while(bin[r]!=r) { r=bin[r]; } int j=x; int k; while(j!=r) { k=bin[j]; bin[j]=r; j=k; } return r;}void merge(int x,int y){ //int fx=findx(x); //int fy=findx(y);//在OJ等不同平台上这样有时W,因为findx()有返回值。 if(x!=y) { bin[x]=y;//节约时间 }}void K(){ int l=1; for(int i=0;i =n) break; if(findx(q[i].x)!=findx(q[i].y)) { merge(q[i].x,q[i].y); l++; sum=sum+q[i].z; } } if(l==n) printf("%d\n",sum); else printf("?\n");}int main(){ while(scanf("%d%d",&m,&n)&&m!=0) { sum=0; for(int i=1;i<=n;i++) bin[i]=i; for(int i=0;i