萌新求助

回复帖子

@胡子 2018-10-21 15:06 回复

rt,努力调试,只有40,两眼一闭,菜到安详QAQ

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define maxn 200010
#define re register
#define FOR(i,l,r) for(re int i=l;i<=r;++i)
using namespace std;

int n,m,c,t,x,y,z,num,need,l,r,mid,anss;
int ans[maxn],head[maxn],a[maxn],ct[maxn],f[maxn],cnt[2];
struct hz{
    int from;
    int to;
    int dis;
    int mode;
    bool operator <(const hz &o)const{
        if(dis+(mode==0?mid:0)==o.dis+(o.mode==0?mid:0))
          return mode<o.mode;
        return dis+(mode==0?mid:0)<o.dis+(o.mode==0?mid:0);
    }
}h[maxn];

inline void in(int &x){ 
    x=0;int f=1;char c=getchar();
    while(c<'0'||c>'9'){
        if(c==-1) return;
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c<='9'&&c>='0'){
        x=(x<<1)+(x<<3)+(c^'0');
        c=getchar();
    }
    x=x*f;
}

inline void out(int a){
    if(a<0){
        a*=-1;
        putchar('-');
    } 
    if(a>=10)out(a/10);
    putchar(a%10+'0');
}

int father(int x){
    if(f[x]!=x) f[x]=father(f[x]);
    return f[x];
}

bool pd(int a,int b){
    int fa=father(a);
    int fb=father(b);
//    cout<<"fa是"<<fa<<" "<<"fb是"<<fb<<endl; 
    if(fa!=fb)
      return true;
    return false;
}

void merge(int a,int b){
    int fa=father(a);
    int fb=father(b);
    f[fa]=fb;
}

bool check(){ //判断白边是否小于要求的个数 
    FOR(i,0,n)
      f[i]=i;
    sort(h+1,h+m+1);
    cnt[0]=cnt[1]=0;
    FOR(i,1,m){
        if(pd(h[i].from,h[i].to)){
//          cout<<h[i].from<<" "<<h[i].to<<endl;
            merge(h[i].from,h[i].to);
            ++cnt[h[i].mode];
        }
        if(cnt[0]+cnt[1]==n-1)
          break;
    }
    if(cnt[0]>=need)
      return true;
    return false;
}

int main(){
    in(n),in(m),in(need);
    FOR(i,1,m){
        in(h[i].from),in(h[i].to),in(h[i].dis),in(h[i].mode);
    }
    l=-200;r=200;
    while(l<=r){
        mid=(l+r)>>1;
        if(check()){
            l=mid+1;
            c=mid;
        }
        else
          r=mid-1;
    }
//  cout<<mid<<endl;
//  FOR(i,1,m)
//    cout<<h[i].from<<" "<<h[i].to<<" "<<h[i].dis<<" "<<h[i].mode<<endl;
    anss=0;
    int res=0;
    FOR(i,0,n)
      f[i]=i;
    mid=c;
    sort(h+1,h+m+1);
    cnt[0]=cnt[1]=0;
    FOR(i,1,m){
        if(pd(h[i].from,h[i].to)){
            if(cnt[0]==need&&h[i].mode==0) //奇怪的地方 
              continue;
            merge(h[i].from,h[i].to);
            anss+=h[i].dis;
            cnt[h[i].mode]++;
            ++res;
        }
        if(res==n-1)
          break;
    }
    out(anss);
}

注意主程序里的“奇怪的地方”

这里如果不加这个特判会导致白边的数量超过限制(照理来说应该不会出现这种情况呀QAQ)

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。