注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Boleyn Su's Blog

 
 
 
 
 

日志

 
 

APIO2008[免费道路/roads]  

2010-04-21 18:02:03|  分类: 信息学 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

先计算至少需要多少鹅卵石路才能使得图连通,设为A,再计算总共有多少鹅卵石路,设为B。有解当且仅当A<=K<=B。

如果有解,先将必须的鹅卵石路加入,然后再加入一些鹅卵石路,使得一共加入了K条鹅卵石路。(注意,它们不能成环)。然后再加公路,同样不能成环。

然后,需要用到并查集。

CODE:

/*

PROGRAM: $PROGRAM

AUTHOR: Su Jiao

DATE: 2010-4-21

DESCRIPTION:

$DESCRIPTION

*/

#include <stdio.h>

#include <string.h>

 

#define MAXN 20000

#define MAXM 100000

 

//begin set

int set[MAXN];

int get_set(int u)

{

    if (set[u]) return set[u]=get_set(set[u]);

    else return u;

}

int is_friend(int u,int v)

{

    return get_set(u)==get_set(v);

}

void union_set(int u,int v)

{

     //if (is_friend(u,v)) return;

     set[get_set(u)]=get_set(v);

}

//end set

 

struct Edge{int u,v,c;};

 

int N,M,K;

Edge edge[MAXM];

bool must[MAXM];

int top;

Edge print[MAXN];

 

int main()

{

    //freopen("roads.in","r",stdin);

    //freopen("roads.out","w",stdout);   

   

    scanf("%d %d %d\n",&N,&M,&K);

    for (int i=0;i<M;i++)

        scanf("%d %d %d\n",&edge[i].u,&edge[i].v,&edge[i].c);

   

    for (int i=0;i<M;i++)

        if (edge[i].c)

           if (!is_friend(edge[i].u,edge[i].v))

              union_set(edge[i].u,edge[i].v);

   

    for (int i=0;i<M;i++)

        if (!edge[i].c)

           if (!is_friend(edge[i].u,edge[i].v))

           {

              union_set(edge[i].u,edge[i].v);

              must[i]=true;

              print[top++]=edge[i];

           }

    if (top>=K) printf("no solution\n");

    else

    {

        memset(set,0,sizeof(set));

        for (int i=0;i<M;i++)

            if (must[i])

               if (!is_friend(edge[i].u,edge[i].v))

                  union_set(edge[i].u,edge[i].v);

        for (int i=0;i<M;i++)

            if (!must[i])

               if (!is_friend(edge[i].u,edge[i].v))

               {

                  union_set(edge[i].u,edge[i].v);

                  print[top++]=edge[i];

               }

        for (int i=0;i<top;i++)

            printf("%d %d %d\n",print[i].u,print[i].v,print[i].c);

    }

    //fclose(stdin);

    //fclose(stdout);

    return 0;

}

 

 

  评论这张
 
阅读(617)| 评论(2)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018