文档章节

【codevs 1001】舒适的路线

LOI_xczhw
 LOI_xczhw
发布于 2016/10/30 09:57
字数 419
阅读 23
收藏 0

嘛嘛……
这题能做?

我滴妈……
按边排一遍序
然后恩恩
选择一条边当做最短的,然后往上找,之后找到的都会是比这条边大的,然后用并查集维护连通性,如果加入一条边之后可以从s走到t,就记录下答案,存下来
然后恩恩约分
233333

我不会约分……

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAXN = 500 + 5;
const int MAXM = 5000 + 5;
struct edge
{
    int f,t,v;
    bool operator < (const edge &b)const
    {
        return v < b.v;
    }
}l[MAXM];
int n,m;
int fa[MAXN];
int rank[MAXN];
void init()
{
    for(int i = 1;i <= n;i ++)
        fa[i] = i;
    memset(rank,0,sizeof(rank));
    return;
}
int find(int x)
{
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}
bool same(int x,int y)
{
    return find(x) == find(y);
}
void merge(int x,int y)
{
    x = find(x);
    y = find(y);
    if(rank[x] < rank[y])
        swap(x,y);
    fa[x] = y;
    if(rank[x] == rank[y])
        rank[y] ++;
    return;
}
struct fs
{
    int fz,fm;
    bool operator < (const fs &b)const
    {
        return fz * b.fm < b.fz * fm;
    }
}zt[MAXM * MAXN];
int tot;
void solve(int s,int t)
{
    tot = 0;
    sort(l + 1,l + m + 1);
    for(int i = 1;i <= m;i ++)
    {
        init();
        zt[tot].fm = l[i].v;
        for(int j = i;j <= m;j ++)
        {
            merge(l[j].f,l[j].t);
            zt[tot].fz = l[j].v;
            if(same(s,t))
                break;
        }
        if(same(s,t))
            tot ++;
    }
    return;
}
int gcd(int a,int b)
{
    if(b == 0)
        return a;
    return gcd(b,a%b);
}
int s,t;
int main()
{
    scanf("%d %d",&n,&m);
    for(int i = 1;i <= m;i ++)
        scanf("%d %d %d",&l[i].f,&l[i].t,&l[i].v);
    scanf("%d %d",&s,&t);
    solve(s,t);
    sort(zt,zt + tot);
    if(!tot)
    {
        puts("IMPOSSIBLE");
        return 0;
    }
    if(zt[0].fz % zt[0].fm == 0)
    {
        printf("%d\n",zt[0].fz / zt[0].fm);
        return 0;
    }
    int k;
    while((k = gcd(zt[0].fm,zt[0].fz)) - 1)
    {
        zt[0].fm /= k;
        zt[0].fz /= k;
    }
    printf("%d/%d\n",zt[0].fz,zt[0].fm);
    return 0;
}

© 著作权归作者所有

LOI_xczhw
粉丝 1
博文 79
码字总数 42567
作品 0
莱芜
私信 提问
codevs4438 YJQ Runs Upstairs

Description 学校科技楼一共有 层,而神犇YJQ每天都在科技楼 楼的机房写代码。这天,他准备从科技楼 楼爬到 楼。有个 连接不同楼层的楼梯,爬每个楼梯需要一定的体力值。楼梯一定是从低处通往高...

aziint
2018/01/06
0
0
splay的各种操作与简易讲解

基本操作 插入 和二叉查找树一样,但是插入完成后要splay一下(即伸展),伸展操作下面有 伸展 查找前驱或后驱 例题:codevs1285/洛谷P2286/bzoj1208 宠物收养所 删除和合并 先把要删除的点s...

litble
2017/07/07
0
0
大数据解读春运:“一票难求”有望缓解

  随着1月3日首趟列车的满载开出,2018年春运正式拉开帷幕。1月4日,360公司发布了《2018春运预测报告》(以下简称:报告)。报告基于历年抢票数据和今年网民搜索趋势指出,不同于2017年的抢...

大数据头条
2018/01/08
0
0
《2018春运大数据预测报告》发布:今年春运将呈现"北松南紧”!

1月4日,360浏览器《2018春运预测报告》正式发布(以下简称:报告)。报告基于历年抢票数据和今年网民搜索趋势指出,不同于2017的抢票难,今年铁路客运能力大幅提升,春运形势整体较为乐观,春...

r6Auo52bK
2018/01/04
0
0
WEB前端开发学习:你思考过为什么JavaScript计算浮点数不准确吗?

Web前端开发工程师是一个很新的职业,是从事Web前端开发工作的工程师。主要进行网站开发,优化,完善的工作。网页制作是Web 1.0时代的产物,那时网站的主要内容都是静态的,用户使用网站的行...

web前端小辰
2018/06/03
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Mybatis Plus删除

/** @author beth @data 2019-10-17 00:30 */ @RunWith(SpringRunner.class) @SpringBootTest public class DeleteTest { @Autowired private UserInfoMapper userInfoMapper; /** 根据id删除......

一个yuanbeth
今天
4
0
总结

一、设计模式 简单工厂:一个简单而且比较杂的工厂,可以创建任何对象给你 复杂工厂:先创建一种基础类型的工厂接口,然后各自集成实现这个接口,但是每个工厂都是这个基础类的扩展分类,spr...

BobwithB
今天
5
0
java内存模型

前言 Java作为一种面向对象的,跨平台语言,其对象、内存等一直是比较难的知识点。而且很多概念的名称看起来又那么相似,很多人会傻傻分不清楚。比如本文我们要讨论的JVM内存结构、Java内存模...

ls_cherish
今天
4
0
友元函数强制转换

友元函数强制转换 p522

天王盖地虎626
昨天
5
0
js中实现页面跳转(返回前一页、后一页)

本文转载于:专业的前端网站➸js中实现页面跳转(返回前一页、后一页) 一:JS 重载页面,本地刷新,返回上一页 复制代码代码如下: <a href="javascript:history.go(-1)">返回上一页</a> <a h...

前端老手
昨天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部