Description
There are n cities in Byteland, labeled by 1 to n. The Transport Construction Authority of Byteland is planning to construct n−1 bidirectional roads among these cities such that every pair of different cities are connected by these roads directly or indirectly.
The engineering company has offered m possible candidate roads to construct. The i-th candidate road will cost ci dollars, and if it is finally constructed, there will be a road connecting the ui-th city and the vi-th city directly. Fortunately, each road has its discounted price, the i-th of which is di.
The Transport Construction Authority of Byteland can buy at most k roads at their discounted prices. Please write a program to help the Transport Construction Authority find the cheapest solution for k=0,1,2,…,n−1.
Input
The first line contains a single integer T (1≤T≤10), the number of test cases. For each test case:
The first line contains two integers n and m (2≤n≤1000, n−1≤m≤200000), denoting the number of cities and the number of candidate roads.
Each of the following m lines contains four integers ui,vi,ci and di (1≤ui,vi≤n, ui≠vi, 1≤di≤ci≤1000), describing a candidate road.
Output
For each test case, output n lines, the i-th (1≤i≤n) of which containing an integer, denoting the cheapest total cost to construct n−1 roads when k=i−1.
It is guaranteed that the answer always exists.
Samples
Input Copy
1 5 6 1 2 1 1 2 3 2 1 2 4 3 2 2 5 4 3 1 3 5 3 4 5 6 1
Output
10 7 6 5 5
给出一个n个点的图，有m条边，每条边有两个价值属性，分别是原始价值和折扣价值，问至少含有i(1 <= i <= n) 条折扣边的最小生成树
官方题解：
将原始价格的边看作是白边，将折扣价格的边看作是黑边，对于每一个输入，黑边和白边连的都是同样的两个端点，所以说同一条边是不可能被选择两次的，所以说问题就相当于是求含有k条折扣边（黑边）的最小生成树问题
设f[x] 是正好包含x条黑边的最小生成树的权值之和，然后这个函数一定是一个上凸的函数，其实这里有wqs二分的意思
wqs是对一个上(上/下)凸的函数二分斜率求出最优解的过程，本题可以说是用到了其思想/doge
考虑两种极端的情况，全选择白边（选择0条黑边）和全选择黑边的两种情形，此时我们对上述情况分别求最小生成树，然后重构输入的两种边，因为我们在求最小生成树的过程当中，将没有用到的非树边去掉是不会影响答案的，将没有用到的非树边去掉也是可以减去一部分复杂度的，经过这样的操作，白边和黑边只会剩下n-1条
然后就很轻松的解决本题啦
#define PII pair<int, int> int fa[maxn]; int n, m; PII save[2007]; struct node { int u, v, w; friend bool operator<(node a, node b) { return a.w < b.w; } } a[maxn], b[maxn]; int find(int x) { if (x == fa[x]) return x; else return fa[x] = find(fa[x]); } bool Union(int x, int y) { int fax = find(x); int fay = find(y); if (fax == fay) return false; fa[fax] = fay; return true; } PII get(int x) { for (int i = 1; i <= n; i++) fa[i] = i; int A = 1, B = 1; int tot = 0, black = 0; while (A < n && B < n) { if (a[A].w <= b[B].w + x) { if (Union(a[A].u, a[A].v)) tot += a[A].w; ++A; } else { if (Union(b[B].u, b[B].v)) tot += b[B].w + x, black++; ++B; } } while (A < n) { if (Union(a[A].u, a[A].v)) tot += a[A].w; ++A; } while (B < n) { if (Union(b[B].u, b[B].v)) tot += b[B].w + x, black++; ++B; } return PII{tot, black}; } int main() { int _ = read; while (_--) { n = read, m = read; // memset(save,-1,sizeof save); for (int i = 1; i <= m; i++) { b[i].u = a[i].u = read; b[i].v = a[i].v = read; a[i].w = read; b[i].w = read; } sort(a + 1, a + 1 + m); for (int i = 1; i <= n; i++) fa[i] = i; for (int i = 1, t = 0; i <= m; i++) { if (Union(a[i].u, a[i].v)) a[++t] = a[i]; } sort(b + 1, b + 1 + m); for (int i = 1; i <= n; i++) fa[i] = i; for (int i = 1, t = 0; i <= m; i++) { if (Union(b[i].u, b[i].v)) b[++t] = b[i]; } for (int i = -1000; i <= 1000; i++) { save[1000 + i] = get(i); } // debug(save[1000].first); // debug(save[1000].second); for (int i = 0; i < n; i++) { int flag = 0; for (int j = -1000; j <= 1000; j++) { if (save[j + 1000].second <= i) { printf("%d\n", save[1000 + j].first - i * j); flag = 1; break; } } if (!flag) puts("-1"); } } return 0; }
代码意思讲解：
bool Union(int x, int y) { int fax = find(x); int fay = find(y); if (fax == fay) return false; fa[fax] = fay; return true; }
如果两个点在求最小生成树的过程中用到了，那么就返回true，否则返回false
get函数是求出将黑色的边权加上一个值x之后的一个花费，我们会这个函数处理出x=-1000->1000的所有情况，然后将信息储存在save中，然后在询问的时候，直接遍历save集合，遇见满足情况的便直接输出，否则输出-1，虽然没有-1的情况/doge
