洛谷 P2619 [国家集训队] Tree I

2026/8/16 22:41:59

题目描述

给你一个无向带权连通图，每条边是黑色或白色。让你求一棵最小权的恰好有 \(need\) 条白色边的生成树。

题目保证有解。

输入格式

第一行 \(V,E,need\) 分别表示点数，边数和需要的白色边数。

接下来 \(E\) 行，每行 \(s,t,c,col\) 表示这边的端点（点从 0 开始标号），边权，颜色（0 白色 1 黑色）。

输出格式

一行，表示所求生成树的边权和。

输入输出样例

输入 #1复制

2 2 1
0 1 1 1
0 1 2 0

输出 #1复制

说明/提示

对于 5% 的数据，\(V≤10\)。

对于另 15% 的数据，\(V≤15\)。

对于 100% 的数据，\(V≤5×10^4,E≤10^5\)。

所有数据边权为 [1,100] 中的正整数。

By WJMZBMR

算法分析

这是本人的第一道国家集训队的难题，偶吼吼吼吼-_-(疯癫)。进入正题，这题很裸，但坑点较多，稍后我会讲，首先处理输入，把输入的数保存到结构体里，然后，先跑一遍最小生成树，我们后得到3种情况：

最小生成树中恰好有\(need\)条白边。
最小生成树中的白边数大于\(need\)。
最小生成树中的白边数小于\(need\)。

第一种情况是最好的，直接输出边权和即可。对于后两种情况，进行二分或暴力，因为白边数大于\(need\)，说明白边边权较小，要加上一些值，反之就减去一些值，二分和暴力枚举的就是加上的这些值，这些值的区间为\([-100,100]\)，最后在求出加上这个值后的最小生成树即可。

二分

二分区间\([-100,100]\)，对每一个值算出每条白边的新权值，跑生成树，最后再还原回来，check一下，对区间中的值取最大值，最后跑一遍生成树，求出权值和，减去\(加上的值\times need\)即可。

复杂度:\(O(log200ElogE)\)

暴力

把二分改成从100到-100依次枚举，遇到第一个满足的值就是二分中的答案，最后也是要减去这个值。

复杂度:\(O(200ElogE)\)

坑点

每跑一遍kruskal都要初始化并查集。
排序的第一关键字是权值，如果权值相等，则白边优先。
输入的节点是以0开始的，要转换成以1开头的。
kruskal中要返回最小生成树的白边数量。
每一次check后都要把白边还原回去。
check中每一次跑出来kruskal的返回值如果大于\(need\)，则返回\(true\)，否则就返回\(false\)。
check中返回的值不要一算出来就返回，还要还原白边。
最后求出值的时候还要再跑一边kruskal，求出权值和。
最后记得减去\(求出来的值\times need\)。
题目保证一定有解，不用特别判断无解。

AC代码

暴力：

#include<bits/stdc++.h>
using namespace std;
struct node{int x,y,z;int op;
};
bool cmp(node a,node b){if(a.z==b.z){return a.op<b.op;//白边优先}else{return a.z<b.z;//权值小的优先}
}
int n,m,k;
int t = 0;
int tot = 0;
int fa[1000005];
node a[1000005];
int sum = 0;
void init(){for(int i = 1; i<=n; i++){fa[i] = i;}
}
int find(int x){if(fa[x]==x){return x;}else{return fa[x] = find(fa[x]);}
}
int kruskal(){init();//初始化sort(a+1,a+1+m,cmp);//排序int cnt = 0;sum = 0;tot = 0;for(int i = 1; i<=m; i++){int x = find(a[i].x);int y = find(a[i].y);if(x!=y){fa[x] = y;sum+=a[i].z;if(a[i].op==0){//统计白边tot++;}cnt++;if(cnt==n-1){//已经联通break;}}}return tot;//返回白边的数量
}
bool check(int x){for(int i = 1; i<=m; i++){//处理白边if(a[i].op==0){a[i].z+=x;}}bool flag = (kruskal()>=k);//判断for(int i = 1; i<=m; i++){//还原白边if(a[i].op==0){a[i].z-=x;}}return flag;
}
int main(){cin>>n>>m>>k;for(int i = 1; i<=m; i++){int x,y,z,op;cin>>x>>y>>z>>op;x++;y++;//处理节点a[i] = node{x,y,z,op};}for(int i = 100; i>=-100; i--){//暴力枚举if(check(i)){t = i;//记录答案break;}}check(t);//算权值和cout<<sum-t*k;//减掉return 0;
}

放一张暴力测出来的时间最大的测试点：

二分

#include<bits/stdc++.h>
using namespace std;
struct node{int x,y,z;int op;
};
bool cmp(node a,node b){if(a.z==b.z){return a.op<b.op;//白边优先}else{return a.z<b.z;//权值小的优先}
}
int n,m,k;
int t = 0;
int tot = 0;
int fa[1000005];
node a[1000005];
int sum = 0;
void init(){for(int i = 1; i<=n; i++){fa[i] = i;}
}
int find(int x){if(fa[x]==x){return x;}else{return fa[x] = find(fa[x]);}
}
int kruskal(){init();//初始化sort(a+1,a+1+m,cmp);//排序int cnt = 0;sum = 0;tot = 0;for(int i = 1; i<=m; i++){int x = find(a[i].x);int y = find(a[i].y);if(x!=y){fa[x] = y;sum+=a[i].z;if(a[i].op==0){//统计白边tot++;}cnt++;if(cnt==n-1){//已经联通break;}}}return tot;//返回白边的数量
}
bool check(int x){for(int i = 1; i<=m; i++){//处理白边if(a[i].op==0){a[i].z+=x;}}bool flag = (kruskal()>=k);//判断for(int i = 1; i<=m; i++){//还原白边if(a[i].op==0){a[i].z-=x;}}return flag;
}
int main(){cin>>n>>m>>k;for(int i = 1; i<=m; i++){int x,y,z,op;cin>>x>>y>>z>>op;x++;y++;//处理节点a[i] = node{x,y,z,op};}int l = -100;int r = 100;while(l<=r){//二分int mid = (l+r)>>1;if(check(mid)){t = mid;//记录答案l = mid+1;}else{r = mid-1;}}check(t);//算权值和cout<<sum-t*k;//减掉return 0;
}

放一张二分测出来的时间最大的测试点：