链接
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2654
神犇题解:http://blog.csdn.net/PoPoQQQ/article/details/47980565
题解
感觉这个题很好玩的样子!
考虑给每一个白边加上一个固定的权值
那么使用白边的数量可以用这个权值来调整
唯一需要注意的就是,这种变化可能不是线性的
也就是说可能会有断层的情况,需要特殊处理一下
值得注意的是,这种方法具有较高的可移植性:
在某一套小火车的模拟题中,一道很恶心的DP也可以用此方法来解决
Code
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 100000+9; struct Edge{int u,v,val,col;}e[N]; int n,m,STA,fa[N]; inline int read(){ char c=getchar(); int ret=0,f=1; while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();} return ret*f; } inline int find(int w) { int f = fa[w], tmp; while (f != fa[f]) f = fa[f]; while (w != f) tmp = fa[w], fa[w] = f, w = tmp; return f; } bool cmp_mx(const Edge &A, const Edge &B) {return A.val < B.val || (A.val == B.val && A.col > B.col);} bool cmp_mn(const Edge &A, const Edge &B) {return A.val < B.val || (A.val == B.val && A.col < B.col);} inline bool judge(int delta) { int cnt = 0; sort(e+1, e+1+m, cmp_mx); for (int i=1;i<=n;i++) fa[i] = i; for (int i=1;i<=m;i++) { if (find(e[i].u) != find(e[i].v)) { fa[find(e[i].u)] = find(e[i].v); cnt += e[i].col; } } if (cnt < STA) return 1; int cost = 0; cnt = 0; sort(e+1, e+1+m, cmp_mn); for (int i=1;i<=n;i++) fa[i] = i; for (int i=1;i<=m;i++) { if (find(e[i].u) != find(e[i].v)) { fa[fa[e[i].u]] = fa[e[i].v]; cnt += e[i].col; cost += e[i].val; } } if (cnt > STA) return 0; else { printf("%d\n",cost-STA*delta); exit(0); } } int main(){ n = read(); m = read(); STA = read(); for (int i=1;i<=m;i++) { e[i].u = read() + 1; e[i].v = read() + 1; e[i].val = read(); e[i].col = read() ^ 1; } int l=-100,r=100,mid; while (l <= r) { mid = l + r >> 1; for (int i=1;i<=m;i++) if (e[i].col) e[i].val += mid; if (judge(mid)) r = mid - 1; else l = mid + 1; for (int i=1;i<=m;i++) if (e[i].col) e[i].val -= mid; } return 0; }