题目描述

有一个国家有N个城市和M条道路，这些道路可能连接相同的城市，也有可能两个城市之间有多条道路。

有一天，有一伙强盗占领了这个国家的所有的道路。他们要求国王献给他们礼物，进而根据礼物的多少而放弃占领某些边。对于每一条道路，强盗都给出了相应的要求，金子gi的数量，银子si的数量。也就是说若国王给强盗G个金子，S个银子，那么他们就会放弃占领满足gi<=G and si<=S 的道路。

现在国王知道金子、银子的单价，他想花费钱财购买金银送给强盗，使强盗放弃一些道路，进而使N个城市能互相到达。但是国王又想花费最少。请你计算最少的花费。

输入格式

第一行有两个整数N和M，表示有N个城市M条道路。

第二行有两个整数G和S，表示购买金子和银子的价格。

以后M行，每行4整数X，Y，g，s，表示这条道路连接X城市和Y城市，要求g个金子，s个银子。

100% N<=200,M<=50000

输出格式

一个整数，表示最少花费。要是没有满足的情况，输出-1。

---

二维限制的最小生成树。

第一眼思路是二分套二分，然后做最小生成树。但是答案显然没有单调性，所以不能这样做。所以我们只能试试暴力。首先要确定的是，购买的金子数量肯定等于某条边的边权，如果小了那可能整个图不连通，大了又浪费了；银子同理。所以我们可以先将所有边按金子数量从小到大排序，然后枚举每条边的边权作为这一次购买的金子数量。那么此时金子数小于等于当前金子数的边都是可以选的，如果我们用这些边构建出了一棵生成树那么就是合法的，否则不合法。

在枚举了每种金子数时，我们为了使代价尽量小，我们需要尽量选银子少的路。所以此时我们将可选的边再按照银子数从小到大进行排序，用Kruskal求出最小生成树。如果成功的话，就用这种方案的代价与答案进行比较取更优。

忽略排序的时间复杂度为O(M^2)，显然太慢。

接下来我们想一下优化。通过分析可以得出，设当前可选的边的集合为A，选中的边的集合为B，也就是说B是当前最优的边。如果后面枚举金子数时加进来新的边，那新的生成树的边肯定也是在新边和B集合中找。也就是说，B在A中的补集已经没有用了，我们将它删掉。那么我们每次需要处理的边最多就只有n-1条，时间复杂度为O(MN)。

那么上代码：

#include
    
     #include
     
      #include
      
       #include
       
        #define maxn 201#define maxm 50001using namespace std; struct edge{    int u,v;    long long g,s;    bool operator<(const edge &e)const{ return g==e.g?s
        
         
          =2;j--) if(e[stack[j]].s