家园重建 （HGOI 2019.2.17 T3）

## 题目大意 给出n个点，m条边，每条边有自己的权值 这个图只可以被分成若干棵树，每棵树上都可以有一个环，问怎样连边使得权值和最大 ## 数据范围 n<=300 ### 解法 很简单，就是一个贪心。按最大生成树去做就可以。 但是要注意，要标记一下一棵树中已经有没有环了。假如一条边链接的两棵树都已经有环了，那么这条边就不能加了。如果一条边链接同一棵树的两点，那么已经有环了也不能连了。 ``` #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define int long long using namespace std; int n,m,ans=0; int fa[310],f[310]; struct Edge { int x,y,z; }e[101000]; bool cmp(Edge a,Edge b) {return a.z>b.z;} int find(int x) { if(fa[x]==x) return x; return fa[x]=find(fa[x]); } signed main() { scanf("%lld%lld",&n,&m); for(int i=1;i<=m;i++) scanf("%lld%lld%lld",&e[i].x,&e[i].y,&e[i].z); sort(e+1,e+m+1,cmp); for(int i=1;i<=n;i++) fa[i]=i; for(int i=1;i<=m;i++) { int x=e[i].x,y=e[i].y; int fx=find(x),fy=find(y); if(fx==fy && !f[fx]) ans+=e[i].z,f[fx]=1; else if(fx!=fy && (!f[fx] || !f[fy])) { ans+=e[i].z; if(!f[fx] && !f[fy]) fa[fx]=fy; else if(f[fx]) fa[fy]=fx; else fa[fx]=fy; } } printf("%lld",ans); return 0; } ```