[APIO2008 roads]并差集、生成树、贪心**

【题目】http://www.apio.olympiad.org/

【算法分析】

使用构造法。

先假设所有的的水泥路都已经连好，然后利用鹅卵路进行合并块，做生成树。

然后用到的这些鹅卵路看作是必需的。

然后清空这个图，并只连上必需的鹅卵路。

一条一条的连鹅卵路使得到达K条。并且整个图没有环。

然后在这个图是用水泥路做生成树就可以了。

【CODE】

#include #include #include const int maxn=21111;
const int maxm=101111;
int n,m,k,haveuse;
int lx[maxm],ly[maxm],lt[maxm],fa[maxn];
bool use[maxm];//必须用的边

void input(){
     scanf("%d%d%d",&n,&m,&k);
     for (int i=1;i<=m;i++) scanf("%d%d%d",&lx[i],&ly[i],&lt[i]);
}

int gf(int k){
    if (fa[k]==k) return k;
    fa[k]=gf(fa[k]);
    return fa[k];
}

void make_need(){
     memset(use,false,sizeof(use));
     for (int i=1;i<=n;i++) fa[i]=i;
     for (int i=1;i<=m;i++)
       if (lt[i] && gf(lx[i])!=gf(ly[i])) fa[fa[lx[i]]]=fa[ly[i]];
     for (int i=1;i<=m;i++)
       if (!lt[i] && gf(lx[i])!=gf(ly[i])){
         fa[fa[lx[i]]]=fa[ly[i]];
         use[i]=true;
         haveuse++;
       }
}

void add_egg_edge(){
     for (int i=1;i<=n;i++) fa[i]=i;
     for (int i=1;i<=m;i++)
       if (use[i]) fa[gf(lx[i])]=gf(ly[i]);
     for (int i=1;i<=m;i++)
       if (haveuse         use[i]=true;
         fa[fa[lx[i]]]=fa[ly[i]];
         haveuse++;
       }
}

void add_water_muddy_edge(){
     for (int i=1;i<=m;i++)
       if (lt[i] && gf(lx[i])!=gf(ly[i])){
         fa[fa[lx[i]]]=fa[ly[i]];
         use[i]=true;
       }
}

void output(){
     for (int i=1;i<=m;i++)
       if (use[i]) printf("%d %d %dn",lx[i],ly[i],lt[i]);
}

int main(){
    freopen("roads.in","r",stdin);
    freopen("roads.out","w",stdout);
    input();
    make_need();
    add_egg_edge();
    if (haveuse!=k) puts("no solutionn");
    else{
         add_water_muddy_edge();
         output();
    }
}