专栏首页calmoundPOj 1797 Heavy Transportation

POj 1797 Heavy Transportation

题意:求从1-n所能承受的最大重量是多少,其最大重量就是1-n通路的最小边

分析:求最大生成树的最小边,排序的时候按照权值从大到小派,然后生成树,知道找到1-n的通路就可以了

#include<stdio.h>
#include<algorithm>
using namespace std;

const int MAXN=1005;
const int INF=0x7fffffff;

int father[MAXN];
int rank[MAXN];
int ans,n,m;

struct Edge
{
    int u,v;
    int w;
}edge[100000];//这里数组开小了re,题目并没有说m的大小,仅仅说了n的大小

bool cmp(Edge a,Edge b)
{
    return a.w>b.w;//这里是关键不是从小到大了
}

void Make_set(int n)
{
    for (int i=0;i<=n;i++)
    {
        father[i]=i;
        rank[i]=0;
    }
}

int Find_set(int x)
{
    int r=x;
    while(r!=father[r])
    {
        r=father[r];
    }
    if(r!=x) father[x]=r;
    return r;
}

void Union(int x,int y)
{
    if(x==y) return ;
    if(rank[x]>rank[y])
    {
        father[y]=x;
    }
    else
    {
        if(rank[x]==rank[y])
        {
            rank[y]++;
        }
        father[x]=y;
    }
}

void Kruskal(int cas)
{
    sort(edge,edge+cas,cmp);
    ans=INF;
    for (int i=0;i<cas;i++)
    {
        int x=Find_set(edge[i].u);
        int y=Find_set(edge[i].v);
        if(x!=y) Union(x,y);
        if(ans>edge[i].w)  ans=edge[i].w;
        if(Find_set(1)==Find_set(n)) break;
    }
}

int main()
{
    int T,i;
    int tes=1;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        for (i=0;i<m;i++)
        {
            scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w);
        }
        Make_set(n);
        Kruskal(m);
        printf("Scenario #%d:\n",tes++);
        printf("%d\n\n",ans);//后面还有一个空白空格,没看见
    }
    return 0;
    
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • zoj 2521 LED Display

    题意:开灯,每个数字都由好几个灯组成,其中一些数字灭掉某些灯可以成为另一个数字,如0灭掉3个灯可以变成7,         现给你一组数字,如何组合可以形成最少...

    用户1624346
  • Sicily 8843 Ranking and Friendship

    http://soj.me/8843 题意:几个人想做好朋友,朋友之间相差位置小于等于k,且长度相同 分析;排序,将长度相同的放在一起。若长度相同,第i个人能放...

    用户1624346
  • How Many Tables (并查集)

    题意:找几个不相连的团体,最后查找发现只要father有几个是自己的,就有几个团队,这个我没想到 #include<stdio.h> #include<stri...

    用户1624346
  • 网络最大流算法—最高标号预流推进HLPP

    吐槽 这个算法。。 怎么说........ 学来也就是装装13吧。。。。 长得比EK丑 跑的比EK慢 写着比EK难 思想 大家先来猜一下这个算法的思想吧:joy...

    attack
  • P1991 无线通讯网

    题目描述 国防部计划用无线网络连接若干个边防哨所。2 种不同的通讯技术用来搭建无线网络; 每个边防哨所都要配备无线电收发器;有一些哨所还可以增配卫星电话。 任意...

    attack
  • Day5下午解题报告1

    预计分数:100+60+30=190 实际分数:100+60+30=190 终于有一道无脑T1了哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈...

    attack
  • 不知道是哪一年的腾讯马拉松题目 照片评级 解题报告

    结果就一不小心看到了这个充满回忆的ACM模式竞赛,还有咱腾讯的,就忍不住看了一下。

    owent
  • 算法训练 区间k大数查询

    接下来m行,每行三个数l,r,K,表示询问序列从左往右第l个数到第r个数中,从大往小第K大的数是哪个。序列元素从1开始标号。

    AI那点小事
  • 9.21模拟赛解题报告

    上来看T1,咦?我好像做过这题在仙人掌上的版本。。树上更简单吧。。写+拍 1h,期间拍出了暴力的两个bug。。。

    attack
  • 【2020HBU天梯赛训练】7-50 部落

    在一个社区里,每个人都有自己的小圈子,还可能同时属于很多不同的朋友圈。我们认为朋友的朋友都算在一个部落里,于是要请你统计一下,在一个给定社区中,到底有多少个互不...

    韩旭051

扫码关注云+社区

领取腾讯云代金券