本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-05 10:21:03

Link

考虑枚举其中一个最大值，然后求在这个最大值下另一个的最大值最小是多少。

后者就是一个每次插入一条边，求最小生成树。

最小生成树的边数是 $\mathrm{O(n)}$ 级别的，且一条边在插入后若有一时刻不存在于最小生成树中，则永远不会出现在最小生成树上。

直接维护边集，插入排序，复杂度是 $\mathrm{O(mn \lpha (n))}$ 。

code

const int N=2e2+5,M=5e4+5;

struct DSU{
	int fa[N],sum[N];
	void init(int n){
		for(int i=1;i<=n;i++)
			fa[i]=i,sum[i]=1; 
	}
	int fd(int x){
		return fa[x]==x?x:fa[x]=fd(fa[x]);
	}
	void merge(int x,int y){
		x=fd(x),y=fd(y);
		if(x!=y){
			if(sum[x]<sum[y])swap(x,y);
			fa[y]=x;
			sum[x]+=sum[y];
		}
	}
}D;

struct edge{
	int u,v,x,y;
	bool operator<(edge ano)const{
		return x<ano.x;
	}
}E[M],e[N];
int tot;
int n;
int tmp[N];

int mx;
bool tag;

void add(int id){
	for(int i=1;i<=tot+1;i++){
		if(e[i].y>E[id].y){
			tot++;
			for(int j=tot;j>=i;j--)
				swap(e[j],e[j+1]);
			e[i]=E[id];
			break;
		}
	}
\/\/	for(int i=1;i<=tot;i++)
\/\/		print(e[i].u),pc(' '),print(e[i].v),pc(' '),print(e[i].x),pc(' '),print(e[i].y),pc('\n');
	D.init(n);
	int cnt=0;
	mx=0;
	tag=0;
	for(int i=1;i<=tot;i++){
		int u=e[i].u,v=e[i].v;
		if(D.fd(u)!=D.fd(v)){
			mx=e[i].y;
			D.merge(u,v);
			tmp[++cnt]=i;
		}
	}
	if(cnt==n-1)
		tag=1;
	for(int i=1;i<=cnt;i++)
		e[i]=e[tmp[i]];
	tot=cnt;
	e[tot+1].y=inf;
}

signed main(){
	n=read();int m=read(),X=read(),Y=read();
	for(int i=1;i<=m;i++)
		E[i]={read(),read(),read(),read()};
	sort(E+1,E+1+m);
	int ans=inf;
	e[1].y=inf;
	for(int i=1;i<=m;i++){
		int j=i;
		while(j<=m&&E[j].x==E[i].x)
			add(j++);
		if(tag)
			ans=min(ans,E[i].x*X+mx*Y);
		i=j-1;
	}print(ans>=inf-2?-1:ans),pc('\n');
	return 0;
}