题解 | #小美的修路#

挺小清新的一道最小生成树。

题意：给你一个图，求这个图的最小生成树。其中图中某些边为必选。

不难想出只要在 ==1 的时候强制加入边进行更新即可。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=200010;
struct node{
	int u,v,w,num;
}e[N];
int n,m,fa[N],vis[N];
int find(int u)
{
	if(fa[u]!=u) return fa[u]=find(fa[u]);
	return u;
}
int ans,cnt,tot;
int cmp(node a,node b)
{
	return a.w<b.w;
}
void kruskal()
{
	sort(e+1,e+1+m,cmp);
	for(int i=1;i<=m;i++)
	{
		int a=find(e[i].u);
		int b=find(e[i].v);
		if(a==b) continue;
		ans+=e[i].w;
		vis[e[i].num]=1;
		tot++;
		fa[a]=b;
		cnt++;
	}
}
int a,b,c,d;
signed main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=1;i<=m;i++)
	{
		cin>>a>>b>>c>>d;
		if(d==1){
			fa[find(a)]=find(b);
			vis[i]=1;
			tot++;
            cnt++;
		}
		e[i].u=a,e[i].v=b,e[i].w=c,e[i].num=i;
	}
	kruskal();
    if(cnt<n-1) cout<<"-1";
    else{
        cout<<tot<<endl;
        for(int i=1;i<=m;i++)
        {
            if(vis[i]) cout<<i<<' ';
         } 
    }
	return 0;
}