- it技术
- HDU1863 ( 畅通工程 )
#include<iostream>
#include<cstdlib>
#include<cstdio>
using namespace std
;
struct Path
{
int x
,y
,c
;
Path() :x(0), y(0), c(0) {}
Path(int xi
, int yi
, int ci
) :x(xi
), y(yi
), c(ci
) {}
};
void merge(Path
* array
,int l
,int mi
,int r
){
Path
* tmp
=new Path
[mi
-l
];
for(int i
=0;i
<mi
-l
;i
++){
tmp
[i
]=array
[l
+i
];
}
int i
=0,j
=mi
,k
=l
;
while(i
<mi
-l
&& j
<r
){
array
[k
++]=(tmp
[i
].c
<=array
[j
].c
)?tmp
[i
++]:array
[j
++];
}
while(i
<mi
-l
){
array
[k
++]=tmp
[i
++];
}
delete []tmp
;
}
void mergesort(Path
* array
,int l
, int r
){
if(r
-l
<2)return;
int mi
=(l
+r
)>>1;
mergesort(array
,l
,mi
);
mergesort(array
,mi
,r
);
merge(array
,l
,mi
,r
);
}
int unionsearch(int* spot
,int root
){
int son
=root
,tmp
;
while(root
!=spot
[root
]){
root
=spot
[root
];
}
while(son
!=root
){
tmp
=spot
[son
];
spot
[son
]=root
;
son
=tmp
;
}
return root
;
}
int main(){
Path
* paths
;
int n
,m
,root1
,root2
,total
,cost
;
int* spot
;
bool flag
=false;
while(true){
scanf("%d %d",&n
,&m
);
if(n
==0)return 0;
paths
=new Path
[n
];
spot
=new int[m
+1];
total
=m
-1;
cost
=0;
flag
=false;
for(int i
=0;i
<n
;i
++){
scanf("%d %d %d",&paths
[i
].x
,&paths
[i
].y
,&paths
[i
].c
);
}
if(n
<m
-1){
printf("?\n");
delete []paths
;
continue;
}
mergesort(paths
,0,n
);
for(int i
=1;i
<m
+1;i
++){
spot
[i
]=i
;
}
for(int i
=0;i
<n
;i
++){
root1
=unionsearch(spot
,paths
[i
].x
);
root2
=unionsearch(spot
,paths
[i
].y
);
if(root1
!=root2
){
spot
[root1
]=root2
;
cost
+=paths
[i
].c
;
total
--;
if(total
==0){
flag
=true;
break;
}
}
}
if(flag
){
printf("%d\n",cost
);
}
else{
printf("?\n");
}
delete []paths
;
}
}
