CF76A gift

题目简述:

给定一个有 \(n\) 个节点， \(m\) 条边的图，每条边有两个权值 \(g\) ,\(s\)。对于图中的一棵生成树，它的花费定义为 \(\max _ {i \in e}{g_i} \times valg + \max _ {i \in e}{s_i} \times vals\) ，求原图中最小花费的一棵生成树。

\(n \le 200\), \(m \le 10^5\)

Solution:

最小生成树好题。

通过题面容易联想到最小生成树，与普通的最小生成树有区别的是，这道题是有两个限制的。

首先考虑消掉一个限制，即枚举 \(maxg\)，同时加入 \(g \le maxg\) 的边。

此时可以直接做一遍 \(\rm Kruskal\) 算 \(maxs\) 的最小值。

但是时间复杂度是 \(O(m^2 log n)\) 的，会爆。

建图可以通过维护指针优化到均摊 \(O(m)\)，排序直接通过插入排序优化到 \(O(m)\)，每次加边， 考虑去除无用状态减少 \(\rm Kruskal\) 的复杂度。

进而有一个比较好猜的结论：

• 对于一条之前不是最小生成树上的边，即使加入一些边之后，它依旧不是最小生成树上的边。

证明如下：

考虑加入一条边 \(x\) 生成树，它必然要替换掉它两端节点到 \(\rm LCA\) 的路径上的某一条边。若它替换掉的是边 \(y\)。此时对花费的贡献是 \(s[x]-s[y]\)。如果贡献大于 \(0\)，替换后会更优，否则不会。

对于刚加入的某一条边 \(x\) ，如果它不在生成树上，那么一定有 \(w[x] > \max(w[i])\) (其中 \(i\) 是路径上的边)。

加入某一条边之后，假如它替换掉了某一条边，那么通过上面的公式，显然不会使得最大值更大。

所以条件不变，不是最小生成树上的边依旧没用。

所以我们只维护原来在最小生成树的边，边的规模由 \(m\) 缩小到 \(n\)。

时间复杂度降为 \(O(nm)\)

code:

#include<bits/stdc++.h>
#define int long long 
using namespace std;

const int N = 200 + 10, M = 5e4 + 10 , INF = 9000000000000000000;
struct Edge{
	int from, to;
	int g, s;
}E[M], E2[M];
int n, m, costs, costg, Ecnt;
bool cmpE(struct Edge E1, struct Edge E2){return E1.g < E2.g;}
int fda[N];

int getfa(int x){return fda[x] = (fda[x] == x)? x : getfa(fda[x]);} 

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n >> m >> costg >> costs;
	int ans = INF;
	for(int i = 1; i <= m; i++)cin >> E[i].from >> E[i].to >> E[i].g >> E[i].s;
	sort(E + 1, E + m + 1, cmpE);
	for(int i = 1; i <= m; i++){
		int pos = ++Ecnt;
		while(pos > 1 &&E2[pos - 1].s > E[i].s){
			E2[pos] = E2[pos - 1];
			pos--;
		}
		E2[pos] = E[i];
		for(int j = 1; j <= n; j++)fda[j] = j;
		int newcnt = 0, cnts = 0, cntg = 0;
		for(int j = 1; j <= Ecnt; j++){
			if(getfa(E2[j].from) == getfa(E2[j].to))continue;
			fda[getfa(E2[j].from)] = getfa(E2[j].to);
			E2[++newcnt] = E2[j];
			cnts = max(cnts, E2[j].s);
			cntg = max(cntg, E2[j].g);
		}
		Ecnt = newcnt;
		if(Ecnt >= n - 1)ans = min(ans, cnts * costs + cntg * costg);
	}
	if(ans != INF)cout << ans;
	else cout << -1;
	
	return 0;
}

换了一个更好看的码风 qwq