OI (×)
CSP (√)
by dead_X @ 2019-08-31 18:43:03
@[dead_X](/space/show?uid=111055) 对不起，除了NOIp以外的其它赛事都还健在
by CreeperLordVader @ 2019-08-31 18:58:05
@[xuanfly](/space/show?uid=183736) 如果您是蒟蒻，我不就是路边摊的吗？QwQ
by Focus_on @ 2019-08-31 19:04:05
改了一下，现在是这样的：
```cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
using namespace std;
int n, m, k, tot, fa[50005], temp, ans, sum;
struct edge {
int u, v, w, col;
} e[200002], f[200002];
int find(int x) { return fa[x] == x ? x : find(fa[x]); }
int cmp(edge a, edge b) {
if (a.w != b.w)
return a.w < b.w;
return a.col < b.col;
}
bool merge(int x, int y) {
x = find(x), y = find(y);
if (x == y)
return 0;
fa[x] = y;
return 1;
}
int check(int mid) {
ans = 0;
sum = 0;
for (int i = 0; i < n; i++) fa[i] = i;
for (int i = 1; i <= m; i++) {
f[i] = e[i];
if (f[i].col == 0)
f[i].w += mid;
}
sort(f, f + m + 1, cmp);
int c = 0;
for (int i = 1; i <= m; i++) {
int u = f[i].u, v = f[i].v;
if (merge(u, v)) {
ans += f[i].w;
c++;
if (f[i].col == 0)
sum++;
}
if (c == n - 1)
break;
}
return sum >= k;
}
int main() {
cin >> n >> m >> k;
for (int i = 1; i <= m; i++) {
cin >> e[i].u >> e[i].v >> e[i].w >> e[i].col;
}
int l = -100, r = 100;
while (l <= r) {
int mid = (l + r) / 2;
if (check(mid)) {
l = mid + 1;
temp = mid;
} else
r = mid - 1;
}
check(temp);
cout << ans - temp * k;
return 0;
}
```
值得高兴的是，我的样例过了，但是仍然是50分，初步判断是merge错了（我同学@[Yang____](/space/show?uid=183743) 说的）
by xuanfly @ 2019-08-31 19:31:39
我 竟然 过了！！！！
zz的我把find写错了！！！！！！！！
```cpp
return x == fa[x] ? fa[x] : fa[x] = find(fa[x]);
```
蒟蒻血泪提示，三目运算符不熟不要用
哭了和同学们查了一下午就是没查出来
------------
最后给大家来一张图吧太高兴了
###### 天依我的
by xuanfly @ 2019-08-31 19:50:22
@[CreeperLordVader](/space/show?uid=68207) 我太蒟了 其他比赛遥不可及
by dead_X @ 2019-08-31 20:31:07