题意简述

题目链接

　　给定一张无向图和两个权值G、S，图中每条边有两个权值au,ag，求一棵生成树，设树边中最大的权值au为A，最大的权值ag为B，需使下式最小化：G*A+S*B。

算法概述

　　【暴力】

　　该题要求一棵特殊的最小生成树，显然Kruskal无法直接求出有二维权值限制的最小生成树，所以我们考虑先固定一维。

　　然后依次枚举每条边，令A等于当前的au，则au固定，再以权值ag为关键字进行Kruskal，最终必然能够求出答案。Kruskal过程中注意，假设当前枚举的边即为最终的树边中权值au最大者，那么则其余边的权值au必然小于等于之，，则可直接筛去权值au大于之者。

　　时间复杂度O(m²logm)。

　　【正解】

　　暴力算法的瓶颈主要在于Kruskal上。我们发现，当前枚举的au为答案的A时，则剩余的树边的权值au必然小于等于之，所以可以想到先以权值au为关键字升序排序，然后开始枚举每条边，固定au，此时我们进行Kruskal时，无需枚举所有的边，由于答案的树边的au必然小于当前边的au，所以直接在排在当前边之前的边中找答案即可。

　　那么考虑维护一个栈，以au为关键字枚举时将该边压入栈中，每次压栈时维护栈中以ag为关键字的单调性，便可省去Kruskal的排序操作。然后以此枚举栈中的边，进行Kruskal，将每一轮Kruskal选出的所有边覆盖到栈中，将栈刷新，即可保证栈中最多只有n-1个元素。

　　如此，可维持时间复杂度在O(nm)。

参考代码

#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
const int N=210,M=5e4+10;
const ll INF=9223372036854775807;
struct Edge{
	int u,v,au,ag;
	bool operator <(const Edge &E)const
	{
		if(au!=E.au)return au=2;j--)
			if(stk[j].ag