为什么会mle啊
  • 板块CF76A Gift
  • 楼主秋水1024
  • 当前回复1
  • 已保存回复1
  • 发布时间2021/8/9 18:36
  • 上次更新2023/11/4 11:24:15
查看原帖
为什么会mle啊
233972
秋水1024楼主2021/8/9 18:36

如标题

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#define ll long long
using namespace std;
const int maxn=205;
const int maxm=50002;
const ll inf=2e18+9;
int n,m,g0,s0,f[maxn],tot,cnt;
ll ans=inf;
struct node{
	int u,v,g,s;
}e[maxm],t[maxn];
bool cmp(node x,node y){
	return x.g<y.g;
}
bool cmp2(node x,node y){
	return x.s<y.s;
}
void set(int x){
	for(int i=1;i<=x;i++)f[i]=i;
	return;
}
int find(int x){
	if(f[x]=x)return x;
	else return f[x]=find(f[x]);
}
int main()
{
	cin>>n>>m>>g0>>s0;
	for(int i=1;i<=m;i++)cin>>e[i].u>>e[i].v>>e[i].g>>e[i].s;
	sort(e+1,e+m+1,cmp);
	for(int i=1;i<=m;i++){
		set(n);
		t[++tot]=e[i]; 
		for(int j=tot;j>1;j--)if(t[j].s<t[j-1].s)swap(t[j],t[j-1]);
		int cnt=0;
		for(int j=1;j<=tot;j++){
			if(find(t[i].u)!=find(t[i].v)){
				f[find(t[i].u)]=find(t[i].v);
				t[++cnt]=t[j];
			}
			if(cnt==n-1)break;
		}
		if(cnt==n-1)ans=min(ans,t[cnt].s*s0*1ll+e[i].g*g0*1ll);
		tot=cnt;
	}
	if(ans==inf)cout<<"-1";
	else cout<<ans;
	return 0; 
 } 

啊啊啊啊啊啊————

2021/8/9 18:36
加载中...