[BZOJ2654]:tree(Kruskal+WQS二分)
题目传送门
题目描述
给你一个无向带权连通图,每条边是黑色或白色。让你求一棵最小权的恰好有need条白色边的生成树。
题目保证有解。
输入格式
第一行V,E,need分别表示点数,边数和需要的白色边数。
接下来E行,每行s,t,c,col表示这边的端点(点从0开始标号),边权,颜色(0白色1黑色)。
输出格式
一行表示所求生成树的边权和。
样例
样例输入:
2 2 1
0 1 1 1
0 1 2 0
样例输出:
2
数据范围与提示
V≤50000,E≤100000,所有数据边权为[1,100]中的正整数。
题解
看到题很恐怖,首先,应该都能想到最小生成树,因为题目上就说了嘛~
但是还有要求,要恰好有need条白边,那么问题就复杂了。
考虑一下,如果我们对所有白边的权值都加或减一个值,然后再跑Kruskal,使用白边的个数就会发生变化,我们就找这样一个值,使使用白边个数为need,然后用这个权值进行计算,将当前情况下所有的边都加进答案,然后最后再减去need×权值,得出的结果极为答案。
发现边权为[1,100]中的正整数,所以时间复杂度O(200×E)。
然而:
发现BZOJ总是能给你意外的惊喜……
优化时间复杂度,考虑二分法:
1.二分法QJ测试点:
然后你能在BZOJ上而分出这个结果:完全无视白边个数这个问题,直接求最小生成树……
内心过于震惊!!!
标程:
说实话,这样有些不道德,毕竟……
无论如何,这道题用来检验你的最小生成树有没有打对还是好的^_^
2.显然上面那种做法很不道德,严重QJ测试点行为!!!那么考虑二分答案进行优化,二分所有白边加或减的这个权值,如果白边个数不足need,则权值要减,反之同理。
时间复杂度O(7×E)。
那么你可能会有疑问,如果出现这样一种情况,当权值为w时,使用白边的个数<need,但是当权值为w-1时,使用白边的个数又>need了,然而题目要求我们求一棵最小权的 恰好 有need条白色边的生成树,那么这种做法的正确性又怎么论证呢?
这样思考,其实当w-1时,增加的白边个数其实也就是权值为w时把它们挤掉的那些黑边,所以其实多出来的白边都可以用黑边代替,所以就不用担心这些问题了。
代码时刻
暴力:
#include<bits/stdc++.h>
using namespace std;
struct rec
{
int s;
int t;
int c;
bool col;
}e[100001],new_e[100001];//e表示原边,new_e用来存储暂时加权值的边
int V,E,need;
int f[50001];
int val;
int sum;
void change(int x,int val)//给new_e赋值
{
new_e[x].s=e[x].s;
new_e[x].t=e[x].t;
new_e[x].c=e[x].c+(e[x].col^1)*val;//如果白边就加上val,如果是黑边则不加
new_e[x].col=e[x].col;
}
bool cmp(rec a,rec b){if(a.c==b.c)return a.col<b.col;return a.c<b.c;}//结构体排序
int find(int x){return f[x]==x?x:f[x]=find(f[x]);}//并查集
bool judge(int x)//判断可不可以
{
int ans=0,cnt=0;
for(int i=1;i<=V;i++)f[i]=i;//并查集记得初始化
for(int i=1;i<=E;i++)change(i,x);
sort(new_e+1,new_e+E+1,cmp);
for(int i=1;i<=E;i++)
{
int xx=find(new_e[i].s);
int yy=find(new_e[i].t);
if(xx==yy)continue;
cnt++;
ans+=new_e[i].col^1;
sum+=new_e[i].c;
f[xx]=yy;
if(cnt==V-1)
if(ans>=need)return 1;
else return 0;
}
}
int main()
{
scanf("%d%d%d",&V,&E,&need);
for(int i=1;i<=E;i++)
{
scanf("%d%d%d%d",&e[i].s,&e[i].t,&e[i].c,&e[i].col);
e[i].s++;
e[i].t++;
}
int ans;
for(int i=100;i>=-100;i--)//爆力枚举答案
{
sum=0;
if(judge(i)){ans=sum-need*i;break;}
}
cout<<ans<<endl;
return 0;
}
QJ测试点,说白了就是Kruskal板子:
#include<bits/stdc++.h>
using namespace std;
struct rec
{
int s;
int t;
int c;
}e[100001];
bool col;
int V,E,need;
int f[50001];
int val;
int ans,cnt;
bool cmp(rec a,rec b){return a.c<b.c;}
int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
int main()
{
scanf("%d%d%d",&V,&E,&need);
for(int i=1;i<=E;i++)
{
scanf("%d%d%d%d",&e[i].s,&e[i].t,&e[i].c,&col);
e[i].s++;
e[i].t++;
}
for(int i=1;i<=V;i++)f[i]=i;
sort(e+1,e+E+1,cmp);
for(int i=1;i<=E;i++)
{
int x=find(e[i].s);
int y=find(e[i].t);
if(x==y)continue;
cnt++;
ans+=e[i].c;
f[x]=y;
if(cnt==V-1)break;
}
cout<<ans;
return 0;
}
正解:
#include<bits/stdc++.h>
using namespace std;
struct rec
{
int s;
int t;
int c;
bool col;
}e[100001],new_e[100001];
int V,E,need;
int f[50001];
int val;
int sum;
void change(int x,int val)
{
new_e[x].s=e[x].s;
new_e[x].t=e[x].t;
new_e[x].c=e[x].c+(e[x].col^1)*val;
new_e[x].col=e[x].col;
}
bool cmp(rec a,rec b){if(a.c==b.c)return a.col<b.col;return a.c<b.c;}
int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
bool judge(int x)
{
int ans=0,cnt=0;
for(int i=1;i<=V;i++)f[i]=i;
for(int i=1;i<=E;i++)change(i,x);
sort(new_e+1,new_e+E+1,cmp);
for(int i=1;i<=E;i++)
{
int xx=find(new_e[i].s);
int yy=find(new_e[i].t);
if(xx==yy)continue;
cnt++;
ans+=new_e[i].col^1;
sum+=new_e[i].c;
f[xx]=yy;
if(cnt==V-1)
if(ans>=need)return 1;
else return 0;
}
}
int main()
{
scanf("%d%d%d",&V,&E,&need);
for(int i=1;i<=E;i++)
{
scanf("%d%d%d%d",&e[i].s,&e[i].t,&e[i].c,&e[i].col);
e[i].s++;
e[i].t++;
}
int lft=-105,rht=105,ans;
while(lft<=rht)//二分答案
{
sum=0;
int mid=(lft+rht)>>1;
if(judge(mid))
{
ans=sum-need*mid;
lft=mid+1;
}
else rht=mid-1;
}
cout<<ans<<endl;
return 0;
}
rp++
最新文章
- 解决checkbox的attr(checked)一直为undefined问题
- sysbench 安装遇到的问题
- vim常用操作
- [leetCode][003] Intersection of Two Linked Lists
- Thread的第五天学习
- (转载)C++lambda表达式
- PHP基本语法的小结
- QT开发pjsip的VOIP,A8平台运行
- OS X Yosemite下安装Hadoop2.5.1伪分布式环境
- angular-ui-tree
- swift 中String常用操作
- GUI Design Studio——如何创建项目展示文件
- 【 js 基础 】Javascript “继承”
- 求二维数组的最大子数组———曹玉松&;&;蔡迎盈
- css position[转
- phacon只能访问index action
- Lomboz插件
- bat 批处理脚本定时执行命令
- windows 安装openssl
- EL与OGNL以及值栈的理解
热门文章
- Process进程 ProcessStartInfo.UseShellExecute 属性
- set的常见用法
- 洛谷 P3388 【模板】割点(割顶)(Tarjan)
- cs244a-Introduction to Computer Networking-Unit2
- npm学习(九)之README.md文件
- luogu P4548 [CTSC2006]歌唱王国
- webstorm 如何去掉下划线
- react-native底部导航栏实现
- hadoop最简伪分布式安装
- DSP学习资料:基于6U VPX的 XC7VX690T+C6678的双FMC接口雷达通信处理板