#include
<
iostream
>
#include
<
cstdio
>
#include
<
map
>
#include
<
algorithm
>
#include
<
string
>
using
namespace
std;
int
par[
5000
],n,m;
struct
In{
int
from,to,len;}s[
100000
];
bool
cmp(In a,In b){
return
a.len
<
b.len;}
void
init(){
int
i;
for
(i
=
1
;i
<=
n;i
++
)par[i]
=
i;}
int
getr(
int
x){
if
(par[x]
==
x)
return
x;
return
par[x]
=
getr(par[x]);}
bool
u(
int
x,
int
y){
int
p,q; p
=
getr(x); q
=
getr(y);
if
(q
==
p)
return
false
; par[p]
=
q;
return
true
;}map
<
string
,
int
>
M;
int
main(){
int
i,j,k,t,x,y,p;
int
ans
=
0
;
string
str1,str2; scanf(
"
%d
"
,
&
t);
while
(t
--
) { scanf(
"
%d%d
"
,
&
n,
&
m); M.clear(); init(); p
=
1
;
for
(i
=
0
;i
<
m;i
++
) { cin
>>
str1
>>
str2
>>
s[i].len; x
=
M[str1]; y
=
M[str2];
if
(x
==
0
) { M[str1]
=
p; x
=
p
++
; }
if
(y
==
0
) { M[str2]
=
p; y
=
p
++
; } s[i].from
=
x; s[i].to
=
y; } sort(s,s
+
m,cmp); n
--
; ans
=
0
;
for
(i
=
0
;i
<
m
&&
n;i
++
) {
if
(u(s[i].from,s[i].to)) { n
--
; ans
+=
s[i].len; } } cout
<<
ans
<<
endl;
if
(t
!=
0
)cout
<<
endl; }
return
0
;}
#include
<
stdio.h
>
#include
<
iostream
>
#include
<
string
.h
>
#include
<
string
>
#include
<
algorithm
>
#include
<
map
>
using
namespace
std;map
<
string
,
int
>
mp;
string
ss;
char
s[
100
];
struct
ppp{
int
u,v,len;} e[
60000
];
bool
cmp(
const
ppp
&
u,
const
ppp
&
v){
return
u.len
<
v.len;}
int
fa[
10000
];
int
finds(
int
x){
if
(fa[x]
!=
x) fa[x]
=
finds(fa[x]);
return
fa[x];}
int
main(){
int
cas,n,m,u,v,len; scanf(
"
%d
"
,
&
cas);
for
(
int
ll
=
1
;ll
<=
cas;ll
++
) {
if
(ll
!=
1
) puts(
""
); scanf(
"
%d%d
"
,
&
n,
&
m); mp.clear();
int
num
=
0
;
for
(
int
i
=
0
;i
<
m;i
++
) { scanf(
"
%s
"
,s); ss
=
s;
if
(mp[ss]
==
0
) mp[ss]
=++
num; u
=
mp[ss]; scanf(
"
%s
"
,s); ss
=
s;
if
(mp[ss]
==
0
) mp[ss]
=++
num; v
=
mp[ss]; scanf(
"
%d
"
,
&
len); e[i].u
=
u;e[i].v
=
v;e[i].len
=
len; } sort(e,e
+
m,cmp);
for
(
int
i
=
1
;i
<=
n;i
++
) fa[i]
=
i;
int
ans
=
0
;
for
(
int
i
=
0
;i
<
m;i
++
) {
int
t1
=
finds(e[i].u);
int
t2
=
finds(e[i].v);
if
(t1
!=
t2) { fa[t1]
=
t2; ans
+=
e[i].len; } } printf(
"
%d\n
"
,ans); }
return
0
;}
#include
<
iostream
>
#include
<
memory.h
>
#include
<
string
>
#include
<
cstdio
>
#include
<
algorithm
>
#include
<
math.h
>
#include
<
stack
>
#include
<
queue
>
#include
<
map
>
using
namespace
std;
const
int
inf
=
1
<<
30
;
const
int
MAX
=
2005
;
int
g[MAX][MAX],dis[MAX];map
<
string
,
int
>
mp;
void
prim(
int
n){
int
i,j,k,ans
=
0
,min_node,maxx;
for
(i
=
1
;i
<=
n;i
++
) dis[i]
=
inf; dis[
1
]
=
0
;
for
(i
=
1
;i
<=
n;i
++
) { maxx
=
inf;
for
(j
=
1
;j
<=
n;j
++
) {
if
(dis[j]
!=-
1
&&
dis[j]
<
maxx) { maxx
=
dis[j]; min_node
=
j; } } ans
+=
maxx; dis[min_node]
=-
1
;
for
(j
=
1
;j
<=
n;j
++
) {
if
(g[min_node][j]
!=
0
&&
dis[j]
>
g[min_node][j]) dis[j]
=
g[min_node][j]; } } cout
<<
ans
<<
endl;}
int
main(){
int
i,j,k,T,n,m,w,flag
=
1
;
char
s1[
10
],s2[
10
]; scanf(
"
%d
"
,
&
T);
while
(T
--
) {
if
(
!
flag) cout
<<
endl; flag
=
0
; memset(g,
0
,
sizeof
(g)); mp.clear(); scanf(
"
%d%d
"
,
&
n,
&
m); k
=
0
;
while
(m
--
) { scanf(
"
%s%s%d
"
,s1,s2,
&
w); i
=
mp[s1];
if
(i
==
0
) { mp[s1]
=++
k; i
=
k; } j
=
mp[s2];
if
(j
==
0
) { mp[s2]
=++
k; j
=
k; }
if
(g[i][j]
==
0
) { g[i][j]
=
g[j][i]
=
w; }
else
{ g[i][j]
=
min(g[i][j],w); g[j][i]
=
g[i][j]; } }
/*
for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { cout<<g[i][j]<<" "; } cout<<endl; }
*/
prim(n); }
return
0
;}
转载于:https://www.cnblogs.com/cyiner/archive/2011/05/24/2055202.html
