求助WA 45pts小号悬棺
查看原帖
求助WA 45pts小号悬棺
795344
lfxxx_楼主2025/1/20 11:14
#include<bits/stdc++.h>
using namespace std;
const int N=5e4+5,M=1e5+5;
int n,m,k;
int fa[N];
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
void merge(int x,int y)
{
	x=find(x),y=find(y);
	if(x!=y)
		fa[x]=y;
}
struct node{int u,v,w,c;}e[M];
bool cmp(node n1,node n2){return n1.w!=n2.w?n1.w<n2.w:n1.c<n2.c;}
int ans=0,cnt=0;
bool check(int mid)
{
	ans=0,cnt=0;
	for(int i=1;i<=n;++i)
		fa[i]=i;
	for(int i=1;i<=m;++i)
		if(e[i].c==0)
			e[i].w+=mid;
	sort(e+1,e+m+1,cmp);
	for(int i=1;i<=m;++i)
	{
		if(find(e[i].u)!=find(e[i].v))
		{
			if(e[i].c==0)
				++cnt;
			ans+=e[i].w;
			merge(e[i].u,e[i].v);
		}
	}
	for(int i=1;i<=m;++i)
		if(e[i].c==0)
			e[i].w-=mid;
	return cnt>=k;
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>m>>k;
	for(int i=1;i<=m;++i)
		cin>>e[i].u>>e[i].v>>e[i].w>>e[i].c,++e[i].u,++e[i].v;
	int l=-114,r=114;
	while(l+1<r)
	{
		int mid=(l+r)>>1;
		if(check(mid))
			l=mid;
		else
			r=mid;
	}
	cout<<ans-k*l;
}
2025/1/20 11:14
加载中...