F.A.Qs Home ProblemSet Status Ranklist Contest LoginRegister
大视野在线测评-欢迎您
[ New Thread ]
Problem 2654 >> 数据过水!建议加强
suxxsfe @ 2020-03-26 14:42:02
[ Quote ] [ Edit ] [ Delete ] 1#
这题数据太水了,建议去洛谷上交

https://www.luogu.com.cn/problem/P2619

我一段代码在bzoj上AC了,洛谷上只有40分

具体错误原因还没找到,找到以后会跟在这个帖子后面
suxxsfe @ 2020-03-26 15:15:36
[ Quote ] [ Edit ] [ Delete ] 2#
找到错了
先放上代码
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<iomanip>
#include<cstring>
#define R register
#define EN std::puts("")
#define LL long long
inline int read(){
int x=0,y=1;
char c=std::getchar();
while(c<'0'||c>'9'){if(c=='-') y=0;c=std::getchar();}
while(c>='0'&&c<='9'){x=x*10+(c^48);c=std::getchar();}
return y?x:-x;
}
int n,m,need;
struct data{
int a,b,w,color;
}p[100006];
int fa[50006];
int find(int k){
return k==fa[k]?k:fa[k]=find(fa[k]);
}
inline int cmp(data aa,data bb){
if(aa.w==bb.w) return aa.color<bb.color;
return aa.w<bb.w;
}
int white;
inline int check(int k){
int ret=0;white=0;
for(R int i=1;i<=m;i++)
if(!p[i].color) p[i].w+=k;
std::sort(p+1,p+1+m,cmp);
for(R int i=1;i<=n;i++) fa[i]=i;
for(R int cnt=0,i=1;cnt<n-1;i++){
R int a=find(p[i].a),b=find(p[i].b);
if(a==b) continue;
white+=(!p[i].color);ret+=p[i].w;
cnt++;fa[a]=b;
}
for(R int i=1;i<=m;i++)
if(!p[i].color) p[i].w-=k;
return white>=need?ret:0;
}
int main(){
n=read();m=read();need=read();
int whitenum=0;
for(R int i=1;i<=m;i++){
p[i].a=read()+1;p[i].b=read()+1;
p[i].w=read();p[i].color=read();
whitenum+=(!p[i].color);
}
R int l=-100,r=100,mid,ans;
while(l<=r){
mid=(l+r)>>1;
int tmp=check(mid);
if(tmp) ans=tmp-need*mid,l=mid+1;
else r=mid-1;
}
std::printf("%d",ans);
return 0;
}
suxxsfe @ 2020-03-26 15:23:13
[ Quote ] [ Edit ] [ Delete ] 3#
其中,二分答案时,更新ans
应该是 ans=tmp-need*mid,l=mid+1;

而不能写成ans=tmp-white*mid,l=mid+1;,其中white为实际选的白边数
suxxsfe @ 2020-03-26 15:27:01
[ Quote ] [ Edit ] [ Delete ] 4#
因为当white>need时存在某些黑边与加权后的白边权值相同,这些白边不能算,只能算need个
suxxsfe @ 2020-03-26 15:27:45
[ Quote ] [ Edit ] [ Delete ] 5#
更为具体的,在这篇题解里有
https://www.luogu.com.cn/blog/ruige818/solution-p2619

上面那段话也是引自这篇题解的评论
suxxsfe @ 2020-03-26 15:27:58
[ Quote ] [ Edit ] [ Delete ] 6#
另外建议加强数据
[Top] [Previous Page] [Next Page]

HOME Back