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

fudq's AC Road

何以解忧,唯有AC!

 
 
 

日志

 
 

hdu 1598  

2012-07-13 14:10:31|  分类: ACM-hdu |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
并查集+贪心
刚开始的时候没有想到用并查集,想到用搜索,但是后来发现用搜索应该会超时,后来看到网上的提示才想到,原来也可以用并查集解决

/*
 * fudq.cpp
 *
 *  Created on: 2012-07-13
 *      Author: fudq
 */
#include<algorithm>
#include<stdio.h>
#include<stdlib.h>
#include<iomanip>
#include<string>
#include<string.h>
#include<math.h>
#include<queue>
#include<map>
#include<stack>
#include<vector>
#include<iostream>
using namespace std;
#define N 1010
struct Edge
{
int s,e,len;
};
Edge edge[N];
int n,m,father[N];

bool cmp(Edge a,Edge b)
{
return a.len<b.len;
}

void init()
{
int i;
for(i=0;i<N;i++)
father[i]=i;
}

int Find(int a)
{
if(a==father[a])
return a;
return Find(father[a]);
}

void Union(Edge a)
{
int x,y;
x=Find(a.s);
y=Find(a.e);
if(x!=y)
father[x]=y;
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("testin.txt","r",stdin);
#endif
    int i,j,a,b,q,min,ans,x,y;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
    for(i=0;i<m;i++)
    scanf("%d%d%d",&edge[i].s,&edge[i].e,&edge[i].len);
    sort(edge,edge+m,cmp);//按路径的从小到大排序,贪心方法,可以减少很多时间
    scanf("%d",&q);
    while(q--)
    {
    scanf("%d%d",&a,&b);
    min=9999999;
    for(i=0;i<m;i++)
    {
    init();
    ans=min;
    for(j=i;j<m;j++)//因为已经排好序了,所以每次只要从后面遍历即可
    {
    Union(edge[j]);
    x=Find(a);
    y=Find(b);
    if(x==y)//如果同属一个集合的话,则表示可以到达
    {
    ans=edge[j].len-edge[i].len;
    break;
    }
    }
    if(min>ans)
    min=ans;
    }
    if(min==9999999)
    printf("-1\n");
    else
    printf("%d\n",min);
    }
    }
    return 0;
}

  评论这张
 
阅读(438)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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