[APIO2008]免费道路

Posted by

题目链接:https://www.luogu.org/problemnew/show/P3623

思路:

使用kruscal算法。

可以先把水泥路加入生成树,然后把必须要加入的鹅卵石路。这时可以判断一下可行性。

以上操作是用来判断连通性的。然后开始构造答案。把必须加入的鹅卵石路加入,若还不满k条,则继续选择。选择完后判断一下可行性。然后加入水泥路即可。

代码:

#include <cstdio>
#include <cctype>
#include <cstring>
#include <iostream>
#include <algorithm>
static const int MAXN=20050;
static const int MAXM=300050;
using namespace std;
struct node{
    int u,v,w;
}e1[MAXM],e2[MAXM];
int n,m,k,u,v,w,cnt,cnt1,cnt2,fa[MAXN];
bool visa[MAXM],visb[MAXM];
inline int read(){
    int x=0;
    bool sign=false;
    char alpha=0;
    while(!isdigit(alpha)) sign|=alpha=='-',alpha=getchar();
    while(isdigit(alpha)) x=(x<<1)+(x<<3)+(alpha^48),alpha=getchar();
    return sign?-x:x;
}
inline int findd(int x){
    int pre,t=x;
    while(x!=fa[x]) x=fa[x];
    while(t!=x){
        pre=fa[t];
        fa[t]=x;
        t=pre;
    }
    return t;
}
inline void kruscal1(){
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=1;i<=cnt2;i++){
        int fx=findd(e2[i].u),fy=findd(e2[i].v);
        if(fx!=fy) fa[fx]=fy;
    }
}
inline void kruscal2(){
    for(int i=1;i<=cnt1;i++){
        int fx=findd(e1[i].u),fy=findd(e1[i].v);
        if(fx!=fy) visa[i]=true,cnt++,fa[fx]=fy;
    }
}
inline bool solve(){
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=1;i<=cnt1;i++) if(visa[i]) fa[findd(e1[i].u)]=findd(e1[i].v);
    for(int i=1;i<=cnt1&&cnt<k;i++){
        if(visa[i]) continue;
        int fx=findd(e1[i].u),fy=findd(e1[i].v);
        if(fx==fy) continue;
        visa[i]=true;
        cnt++;
        fa[findd(e1[i].u)]=findd(e1[i].v);
    }
    if(cnt<k) return true;
    for(int i=1;i<=cnt2;i++){
        int fx=findd(e2[i].u),fy=findd(e2[i].v);
        if(fx!=fy){
            fa[fx]=fy;
            visb[i]=true;
        }
    }
    return false;
}
int main(){
    n=read();m=read();k=read();
    for(int i=1;i<=m;i++){
        u=read();v=read();w=read();
        w==0?(e1[++cnt1].u=u,e1[cnt1].v=v,e1[cnt1].w=w):(e2[++cnt2].u=u,e2[cnt2].v=v,e2[cnt2].w=w);
    }
    kruscal1();
    kruscal2();
    if(cnt>k) return 0&printf("no solution\n");
    if(solve()) return 0&printf("no solution\n");
    for(int i=1;i<=cnt1;i++) if(visa[i]) printf("%d %d %d\n",e1[i].u,e1[i].v,e1[i].w);
    for(int i=1;i<=cnt2;i++) if(visb[i]) printf("%d %d %d\n",e2[i].u,e2[i].v,e2[i].w);
    return 0;
}

 

 

Leave a Reply

电子邮件地址不会被公开。 必填项已用*标注