有一个国家有N个城市和M条道路,这些道路可能连接相同的城市,也有可能两个城市之间有多条道路。 有一天,有一伙强盗占领了这个国家的所有的道路。他们要求国王献给他们礼物,进而根据礼物的多少而放弃占领某些边。对于每一条道路,强盗都给出了相应的要求,金子gi的数量,银子si的数量。也就是说若国王给强盗G个金子,S个银子,那么他们就会放弃占领满足gi<=G and si<=S 的道路。 现在国王知道金子、银子的单价,他想花费钱财购买金银送给强盗,使强盗放弃一些道路,进而使N个城市能互相到达。但是国王又想花费最少。请你计算最少的花费。
Input
第一行有两个整数N和M,表示有N个城市M条道路。
第二行有两个整数G和S,表示购买金子和银子的价格。
以后M行,每行4整数X,Y,g,s,表示这条道路连接X城市和Y城市,要求g个金子,s个银子。
100% N<=200,M<=50000
Output
一个整数,表示最少花费。要是没有满足的情况,输出-1。
Sample Input
3 3
2 1
1 2 10 15
1 2 4 20
1 3 5 1
Sample Output
30
题目大概是说,从一堆边里面选出若干条,使得整个图联通,且要求选出的边中最大的g和s最小。
最小生成树问题。
把所有的边按照g值升序排序,然后从前往后枚举,每次枚举到一个新的值就把所有能用的边全部放到另外一个数组里,然后(kruskal)再把这个数组按照s值升序排序,做一遍最小生成树,直到符合条件为止。
几个优化:
首先,在我们加入一条新的边的时候,其实没必要用sort扫一遍,可以把它当成一个栈,从栈顶往下扫,如果新加入的这条边下面那条边的s值大于新加入的这条边的s值,那么就把他们的位置互换。
然后,在过程中我们发现有一些边如果这次没用到,那么接下来也不可能会用到,所以就没有必要保留,直接舍弃就好,还能节约空间。也就是说,我们把每次选中的边都放到数组的最前端,加一个指针就好。
代码如下:
#include<bits/stdc++.h> using namespace std; struct edge { int x, y; long long g, s; } e[50010]; int n, m; long long g, s; int st[210], top, cnt; long long ans = 0x7fffffffffffffffll; int fa[210]; inline long long read() { long long x = 0, f = 1; char ch = getchar(); while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();} while (ch >= '0' && ch <= '9') {x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar();} return x * f; } void init() { for (int i = 1; i <= n; i++) fa[i] = i; } bool cmp_g(edge a, edge b) { if (a.g == b.g) return a.s < b.s;//金子数量相同按银子从小到大 return a.g < b.g; } int find(int x) { if (x == fa[x]) return x; return fa[x] = find(fa[x]); } int main() { // freopen("data.in", "r", stdin); n = read(), m = read(), g = read(), s = read(); for (int i = 1; i <= m; i++) { e[i].x = read(), e[i].y = read(), e[i].g = read(), e[i].s = read(); } sort(e + 1, e + m + 1, cmp_g); //按金子的数量,从小到大 for (int i = 1; i <= m; i++) { init();//初始化,并查集清空 ,因为每加一条边就要求一次最小生成树 //维护一个栈,栈里是组成最小生成树的边 st[++top] = i, cnt = 0;//加入一条新边 //对于新边,所需金子数量增加,我们当然希望银子数量减少才好 for (int j = top; j >= 2; j--) { if (e[st[j]].s < e[st[j - 1]].s) { swap(st[j], st[j - 1]); }//扫栈 ,所需金子数量确定的情况下,银子所需数越小的越往栈底走 } //kruskal,每加一条边,就做一次mst for (int j = 1; j <= top; j++) { int eu = find(e[st[j]].x), ev = find(e[st[j]].y); if (eu == ev) continue; fa[ev] = eu; st[++cnt] = st[j];//将用到的边放到st数组中 if (cnt == n - 1) break; } if (cnt == n - 1) { //cout<<e[i].g<<" "<<e[st[cnt]].s<<endl; ans = min(ans, e[i].g * g + e[st[cnt]].s * s); //更新答案 } top = cnt; } if (ans == 0x7fffffffffffffffll) puts("-1"); else printf("%lld", ans); return 0; }