bzoj1083 [SCOI2005]繁忙的都市(最小生成树)

摘要:
Description城市C是一个非常繁忙的大都市,城市中的道路十分的拥挤,于是市长决定对其中的道路进行改造。3.在满足要求1、2的情况下,改造的那些道路中分值最大的道路分值尽量小。接下来m行是对每条道路的描述,u,v,c表示交叉路口u和v之间有道路相连,分值为c。Output两个整数s,max,表示你选出了几条道路,分值最大的那条道路的分值是多少。SampleInput45123145247236348SampleOutput36分析:最小生成树只要知道了算法,就简单了但时要怎么看出算法呢?

Description
城市C是一个非常繁忙的大都市,城市中的道路十分的拥挤,于是市长决定对其中的道路进行改造。城市C的道
路是这样分布的:城市中有n个交叉路口,有些交叉路口之间有道路相连,两个交叉路口之间最多有一条道路相连
接。这些道路是双向的,且把所有的交叉路口直接或间接的连接起来了。每条道路都有一个分值,分值越小表示这
个道路越繁忙,越需要进行改造。但是市政府的资金有限,市长希望进行改造的道路越少越好,于是他提出下面的
要求: 1. 改造的那些道路能够把所有的交叉路口直接或间接的连通起来。 2. 在满足要求1的情况下,改造的
道路尽量少。 3. 在满足要求1、2的情况下,改造的那些道路中分值最大的道路分值尽量小。任务:作为市规划
局的你,应当作出最佳的决策,选择那些道路应当被修建。

Input
第一行有两个整数n,m表示城市有n个交叉路口,m条道路。接下来m行是对每条道路的描述,u, v, c表示交叉
路口u和v之间有道路相连,分值为c。(1≤n≤300,1≤c≤10000)

Output
两个整数s, max,表示你选出了几条道路,分值最大的那条道路的分值是多少。

Sample Input
4 5
1 2 3
1 4 5
2 4 7
2 3 6
3 4 8

Sample Output
3 6

分析:
最小生成树
只要知道了算法,就简单了

但时要怎么看出算法呢?
最小生成树一般符合一下几个条件:

  • 有边权的无向图
  • 需要找到几条边,使点之间直接或间接连接
  • 找到的边最少,边权之和最小
//这里写代码片
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;

const int N=303;
int n,tot=0,st[N],m,fa[N],maxx;
struct node{
    int x,y,v,nxt;
};
node way[20010];

int cmp(const node &a,const node &b)
{
    return a.v<b.v;
}

void add(int u,int w ,int z)
{
    tot++;
    way[tot].x=u;way[tot].y=w;way[tot].nxt=st[u];way[tot].v=z;st[u]=tot;
}

int find(int a)
{
    if (fa[a]!=a) fa[a]=find(fa[a]);
    return fa[a];
}

void unionn(int f1,int f2){fa[f1]=f2;}

void doit()
{
    for (int i=1;i<=n;i++) fa[i]=i;
    sort(way+1,way+1+m,cmp);
    int o=0;
    for (int i=1;i<=m;i++)
    {
        int f1=find(way[i].x);
        int f2=find(way[i].y);
        if (f1!=f2)
        {
            unionn(f1,f2);
            maxx=max(maxx,way[i].v);
            o++;
        }
        if (o==n-1) break;
    }
    printf("%d %d",n-1,maxx);
}

int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++)
    {
        int u,w,z;
        scanf("%d%d%d",&u,&w,&z);
        add(u,w,z);
    }
    doit();
    return 0;
}

免责声明:文章转载自《bzoj1083 [SCOI2005]繁忙的都市(最小生成树)》仅用于学习参考。如对内容有疑问,请及时联系本站处理。

上篇ListView实现点击列排序Debian初安装下篇

宿迁高防,2C2G15M,22元/月;香港BGP,2C5G5M,25元/月 雨云优惠码:MjYwNzM=

相关文章

Kruskal算法&amp;amp;Prim算法

最小生成树是什么? Kruskal算法 图文转载自a2392008643的博客 此算法可以称为“加边法”,初始最小生成树边数为0,每迭代一次就选择一条满足条件的最小代价边,加入到最小生成树的边集合里。 把图中的所有边按代价从小到大排序; 把图中的n个顶点看成独立的n棵树组成的森林; 按权值从小到大选择边,所选的边连接的两个顶点ui,viui,vi,应属于...

[转载]最小生成树-Prim算法和Kruskal算法

转载地址:http://www.cnblogs.com/biyeymyhjob/archive/2012/07/30/2615542.html  自己在学,感觉这个讲的很不错,就转载了。 Prim算法 1.概览 普里姆算法(Prim算法),图论中的一种算法,可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中,不但包括了连通图里的所有顶点...

poj2349最小生成树prim算法

题目:有s个satellite channels,但有p(p>s)个地方,若任意两个地方有satellite channels,则无视该距离,并且剩余的地方只能与其他地方通过无线电连接,需要距离,且需要的距离只与最大距离有关,问该最大距离的最小值(大概是这样啦)分析:实际上就是求最小生成树中的第p-s大的数,可以先通过prim算法生成最小生成树,然后...

【最小生成树】口袋的天空

口袋的天空 背景 小杉坐在教室里,透过口袋一样的窗户看口袋一样的天空。 有很多云飘在那里,看起来很漂亮,小杉想摘下那样美的几朵云,做成棉花糖。 描述 给你云朵的个数N,再给你M个关系,表示哪些云朵可以连在一起。 现在小杉要把一些云朵连在一起,做成K个棉花糖,一个棉花糖最少要用掉一朵云,小杉想知道他怎么连,花费的代价最小。 格式 输入格式 每组测试数据的第一行...

BZOJ2594 [Wc2006]水管局长数据加强版 【LCT维护最小生成树】

题目 SC省MY市有着庞大的地下水管网络,嘟嘟是MY市的水管局长(就是管水管的啦),嘟嘟作为水管局长的工作就是:每天供水公司可能要将一定量的水从x处送往y处,嘟嘟需要为供水公司找到一条从A至B的水管的路径,接着通过信息化的控制中心通知路径上的水管进入准备送水状态,等到路径上每一条水管都准备好了,供水公司就可以开始送水了。嘟嘟一次只能处理一项送水任务,等到...

【洛谷P2504】聪明的猴子 最小瓶颈树

题目大意:给定一张 N 个顶点的完全图,边有边权,求该完全图的一棵最小瓶颈树。 最小瓶颈树:一棵最大边权值在同一张图的所有生成树中最小,即:最大边权值最小的生成树,其值为该树的最大边权的权值。引理1:最小生成树一定是一棵最小瓶颈树。证明:若最小生成树不是最小瓶颈树,则意味着存在一条边的权值大于最小瓶颈树的最大边权值,那么将 MST 的该边去掉,则将一棵树变...