题解：最大生成树加判环……
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28 |
#include <cstdio>#include <algorithm>using
namespace std;struct
node{int
a,b,l;}seg[100005];bool
cmp(node a,node b){return
a.l>b.l;}int ans,m,n,f[10005],mark[10005];int sf(int
x){return
f[x]==x?x:f[x]=sf(f[x]);}int main(){ while(scanf("%d%d",&n,&m)){ if
(m==0&&n==0)break; ans=0; for(int
i=0;i<n;i++)f[i]=i,mark[i]=0; for(int
i=0;i<m;i++)scanf("%d%d%d",&seg[i].a,&seg[i].b,&seg[i].l); sort(seg,seg+m,cmp); for(int
i=0;i<m;i++){ int
q=sf(seg[i].a),w=sf(seg[i].b); if(q==w){ if(mark[q]==0&&mark[w]==0) ans+=seg[i].l,mark[q]=1; continue; }else{ if(mark[q]==1&&mark[w]==1)continue; if(mark[q]==1||mark[w]==1)ans+=seg[i].l,f[q]=w,mark[w]=1; else
f[q]=w,ans+=seg[i].l; } } printf("%d\n",ans); } return
0;} |
HDU 3367 Pseudoforest,布布扣,bubuko.com
原文：http://www.cnblogs.com/forever97/p/3604538.html