精华内容
下载资源
问答
  • 修建的意思
    2019-04-21 16:45:36

    小明来到一个由 n 个小岛组成的世界,岛与岛之间通过修建桥,来让岛上的居
    民可以去其他的小岛。已知已经修建了 m 座桥,居民们想让小明帮忙计算,最
    少还要在修建几座桥,居民们才能去所有的岛。
     输入格式: 第一行输入俩个数字 n,m(1≤n≤1000, 0≤m≤n×(n−1)/2),
    分别代表岛的个数,和已经修建的桥的个数,岛的编号分别是 1…n。接下来的
    m 行,每行俩个数字,代表这俩个编号的岛之间已经有一座桥了。
     输出格式: 输出最少还需要修建多少座桥,居民才能去所有的岛。
     样例输入
     5 4
     1 2
     2 3
     4 5
     1 3
     样例输出
     1

    用visit[i],来记录第i个岛有没有走过,1代表走过0则没有。用res记录有几个分离出来独立的连接岛。(所谓连接岛的意思就是eg :1 2 3是一个连接岛代表这三个岛互相联通,也就是联通图。4,5是一个连接岛。并且一个连接岛是不可能到另一个连接岛上去的)
    这道题用图的深度搜索去做。循环遍历这n个岛,每发现一个岛没有走过就让res加一,然后再深度搜索这个岛,将搜索到的岛都标记为已经走过,于是就创建了一个连接岛。

    #include <iostream>
    #include <vector>
    #include <string.h>
    using namespace std;
    const int MAX=1001;
    
    vector<int> pos[MAX];
    int visit[MAX];
    void dfs(int m)
    {
        visit[m]=1;
        for(int i=0;i<pos[m].size();i++)
        {
            if(!visit[pos[m][i]])
                dfs(pos[m][i]);
        }
    }
    int main()
    {
        int n,m;
        cin>>n>>m;
        memset(visit,0,sizeof(visit));
        for(int i=0;i<m;i++)
        {
            int a,b;
            cin>>a>>b;
            pos[a].push_back(b);
            pos[b].push_back(a);
        }
        int res=0;
        for(int i=1;i<=n;i++)
        {
            if(!visit[i])
            {
                res++;
                dfs(i);
            }
        }
        cout<<res-1;
        return 0;
    }
    
    
    更多相关内容
  • 大概意思就是:求一条最短路径,其中 k 条路免费,求最小的值。 解题思路: 这道题给我的感觉就是——不好做,像最短路径,又不像最短路径。 很明显,这 k 条免费的路是个麻烦——不能直接用最短路。 暴力...

    目录:

    前置知识

    题目描述

    解题思路

    AC 代码


    前置知识:

            最短路径(Dijkstra) 、 二分算法 、 链式前向星

    题目描述:

            大概意思就是:求一条最短路径,其中 k 条路免费,求最小的值。

    解题思路:

            这道题给我的感觉就是——不好做,像最短路径,又不像最短路径。

            很明显,这 k 条免费的路是个麻烦——不能直接用最短路。   

            暴力免费的路的条数肯定过不了,数据超过了 200 也不能用 Floyd ,还是考虑稳定的 Dijkstra 算法。既然暴力免费路的条数不行,那我们就考虑暴力答案。

            这样以来,问题就转化成了二分答案:假定第 k+1 条路径的最短路的第 k+1 条路长度为 ans,只需要计算图中能否找到一条路径,满足这条路径上的边的长度大于 ans 的数量小于等于 k 条即可。

            至于如何求这条路经,就只需要把每一个 ans 进行一遍 Dijkstra ,考虑到时间复杂度可能超限,所以采用链式前向星来存储图。 

    AC 代码:

    #include<iostream>
    #include<cstdio>
    #include<cmath>
    #include<algorithm>
    #include<map>
    #include<vector>
    #include<string>
    #include<cstring>
    #include<queue>//头文件 
    using namespace std;
    inline int read()//快读的模板 
    {
        int num=0,w=1;
        char ch=getchar();
        while(ch<'0'||ch>'9')
        {
            if(ch=='-') w=-1;
            ch=getchar();
        }
        while(ch>='0'&&ch<='9')
        {
            num=(num<<1)+(num<<3)+ch-'0';
            ch=getchar();
        }
        return num*w;
    }
    int head[10001],tot;//链式前向星 
    struct node//链式前向星 
    {
    	int from;
    	int to;
    	int w;
    }g[10001];
    int n,p,k; 
    int u,v,w;
    int l,r,mid;//二分的一些变量 
    int ans;
    bool vis[10001];//该点是否在这条路径中 
    int dis[10001];//长度大于ans的边的数量 
    inline void add(int x,int y,int w)//链式前向星 
    {
    	tot++;
    	g[tot].from=head[x];
    	g[tot].to=y;
    	g[tot].w=w;
    	head[x]=tot; 
    	return;
    }
    priority_queue<pair<int,int> >q;//队列优化 
    inline bool dijkstra(int now)//队列优化的 Dijkstra 
    {
    	memset(vis,0,sizeof(vis));//每次都要初始化一遍 
    	memset(dis,0x3f3f3f,sizeof(dis));//每次都要初始化一遍 
    	dis[1]=0;//源点为零 
    	q.push(make_pair(dis[1],1));
    	while(!q.empty())
    	{
    		int t=q.top().second;
    		q.pop();
    		if(vis[t])
    		{
    			continue;
    		}
    		vis[t]=1;
    		for(int i=head[t];i!=-1;i=g[i].from)//按照题目要求进行最短路径 
    		{
    			if(dis[g[i].to]>dis[t]+(g[i].w>now))//其中 g[i].w>now 如果为真返回1,否则返回0 
    			{
    				dis[g[i].to]=dis[t]+(g[i].w>now);
    				q.push(make_pair(-dis[g[i].to],g[i].to));
    			}
    		}
    	}
    	return dis[n]<=k;//判断是否为符合要求 
    }
    int main()
    {
    	//freopen(".in","r",stdin);
    	//freopen(".out","w",stdout);
    	memset(head,-1,sizeof(head));//个人习惯初始化为-1 
    	n=read();
    	p=read();
    	k=read();
    	for(int i=1;i<=p;i++)
    	{
    		u=read();
    		v=read();
    		w=read();
    		add(u,v,w);
    		add(v,u,w);
    	}
    	ans=0x7f7f7f;
    	r=1000000000;
    	while(l<=r)//进行二分答案 
    	{
    		mid=(l+r)>>1;
    		if(dijkstra(mid))
    		{
    			ans=mid;
    			r=mid-1;
    		}
    		else
    		{
    			l=mid+1;
    		}
    	}
    	if(ans==0x7f7f7f)//注意:如果没有符和的答案(也就是1和n不连通)要输出-1 
    	{
    		printf("-1\n");
    		return 0; 
    	}
    	printf("%d\n",ans);//输出 
    	//fclose(stdin);
    	//fclose(stdout);		
    	return 0;//完结撒花
    }

    展开全文
  • 公路修建 2 分析 这题特别的地方就是边多,5000×50005000\times 50005000×5000的边用kruscal空间不对. 主要空间瓶颈就是边的权是存不下来的,然而kruscal是需要计算然后再sort一遍的,我们想到prim. 其实prim算法我...

    1 题面

    公路修建

    2 分析

    这题特别的地方就是边多, 5000 × 5000 5000\times 5000 5000×5000的边用kruscal空间不对.
    主要空间瓶颈就是边的权是存不下来的,然而kruscal是需要计算然后再sort一遍的,我们想到prim.
    其实prim算法我没有怎么选过,这题就当作prim练习题叭QAQ

    3 具体实现

    prim的主要思想就是对于已联通的点集 u u u与未联通的点集 v v v之间的所有边,选择一个最小的选上,这样就是最小的了.
    那为什么这样是对的呢?
    这里给出一个感性证明:对于每次选择,都将一个新点加入点集 u u u中,我们知道每个点都是要进入 u u u中的,而我们的算法又选的是最小的边,那么整个生成树一定就是最小的.

    解释一下变量的意思:
    pos代表从 u u u v v v新加入的那个点
    vis[i]代表i是否在点集 u u u
    ans是最小生成树的大小
    //dis是这一题要求的距离

    void prim(){
        int pos=0;
        for (int i=1; i<=n; i++) {
            double minx=inf;
            for (int j=1; j<=n; j++) {
                if (!vis[j] && dis[j]<minx) {
                    minx=dis[j];
                    pos=j;
                }
            }
            ans+=minx;
            vis[pos]=1;
            for (int j=1; j<=n; j++) {
                double d=cal(pos, j);
                dis[j]=std::min(dis[j],d);
            }
        }
    }
    

    4 参考代码

    #include <iostream>
    #include <cstdio>
    #include <cmath>
    #include <cstring>
    #define inf 99999999.0
    #define maxn 5001
    int n;
    double dis[maxn],ans;
    bool vis[maxn];
    struct node{
        int x,y;
    }nodes[maxn];
    double cal(int i,int j){
        return sqrt((double)(nodes[i].x-nodes[j].x)*(nodes[i].x-nodes[j].x)+(double)(nodes[i].y-nodes[j].y)*(nodes[i].y-nodes[j].y));
    }
    void prim(){
        int pos=0;
        for (int i=1; i<=n; i++) {
            double minx=inf;
            for (int j=1; j<=n; j++) {
                if (!vis[j] && dis[j]<minx) {
                    minx=dis[j];
                    pos=j;
                }
            }
            ans+=minx;
            vis[pos]=1;
            for (int j=1; j<=n; j++) {
                double d=cal(pos, j);
                dis[j]=std::min(dis[j],d);
            }
        }
    }
    int main(){
        scanf("%d",&n);
        for (int i=1; i<=n; i++) {
            scanf("%d%d",&nodes[i].x,&nodes[i].y);
            dis[i]=inf;
        }
        dis[1]=0;
        prim();
        printf("%.2lf\n",ans);
        return 0;
    }
    
    
    展开全文
  • 计蒜客—— 修建大桥

    2017-12-07 19:07:29
    蒜头君来到一个由 nn 个小岛组成的世界,岛与岛之间通过修建桥,来让岛上的居民可以去其他的小岛。已知已经修建了 mm 座桥,居民们想让蒜头君帮忙计算,最少还要在修建几座桥,居民们才能去所有的岛。 输入格式 ...

    蒜头君来到一个由 nn 个小岛组成的世界,岛与岛之间通过修建桥,来让岛上的居民可以去其他的小岛。已知已经修建了 mm 座桥,居民们想让蒜头君帮忙计算,最少还要在修建几座桥,居民们才能去所有的岛。

    输入格式

    第一行输入俩个数字 nnmm,分别代表岛的个数,和已经修建的桥的个数,岛的编号分别是 1 \ldots n1n。(1 \leq n \leq 10001n10000 \leq m \leq n \times (n-1) / 20mn×(n1)/2)接下来的 mm 行,每行俩个数字,代表这俩个编号的岛之间已经有一座桥了。

    输出格式

    输出最少还需要修建多少座桥,居民才能去所有的岛。

    样例输入

    5 4
    1 2
    2 3
    4 5
    1 3

    样例输出

    1

    一开始没看懂,不知道是用图的深度遍历还是广度遍历,后来仔细想了一下,发现先建立一个无向图的邻接表然后再 深度遍历 这个表,从1这个村庄开始访问,每次访问到一个未标记的村,有效的桥数加1(因为最少的桥数肯定是n-1座,像一维数轴那样排布),
    所以最后输出n-1-x即可。 (有更简单的方法也求教。)
    具体代码如下:
    #include<cstring>
    #include<iostream>
    using namespace std;
    const int max_n=100000;
    const int max_m=100000;
    struct edge{
        int v,next ;
    }e[max_m];
    int p[max_n],eid,x=0;
    void init(){
        memset(p,-1,sizeof(p));
        eid=0;
    }
    void insert(int u,int v){
        e[eid].v=v;
        e[eid].next=p[u];
        p[u]=eid++;
    }
    bool vis[max_n];
    void dfs(int u){
       // cout<<"vis"<<u<<endl;
        vis[u]=true;
        for(int i=p[u];i!=-1;i=e[i].next){
            if(!vis[e[i].v]){
                x++;
                dfs(e[i].v);
            }
        }
    }
    int main(){
        int n,m;
        cin>>n>>m;
        init();
        memset(vis,false,sizeof(vis));
        for(int i=0;i<m;i++)
        {
            int a,b;
            cin>>a>>b;
            insert(a,b);
            insert(b,a);
        }
        for(int i=1;i<=n;i++)
            dfs(i);
        cout<<n-x-1;
    }


    展开全文
  • [ NOI 2011 ] 道路修建

    2018-09-20 20:03:00
    \(\\\) \(Description\) 一棵\(N\)个节点的树,每条边有边权,修建一条边的代价是: 这条边的边权\(\times\)修建好的树中,由该条边分开的两个子图节点数之差的绝对值 ...弃疗看讨论发现原来是说的这个意思...
  • 这句话的意思就是树上的任意一个节点它的儿子最多两个,这意味着什么? (不知道) 我们分析一下性质,对于一棵树中的任意一个节点(把个体先分析)我们可以知道抠链要么是直接在内部两个儿子通过父亲相连拼接成一...
  • 最小堆dijkstra算法解ccf-csp的地铁修建问题
  • 这道题有一点点树上dp的意思(大佬轻喷 我刚拿到这道题的时候毫无头绪,只知道这道题要二分答案 为什么是二分答案??? 题目: 目前赛道修建的方案尚未确定。你的任务是设计一 种赛道修建的方案,使得修建的 m 条...
  • 1951年开始修建雅安至拉萨的康藏公路。西康撤省后两条路并称川藏公路。川藏线以其特有的魅力,虽遗世而独立,却吸引着一颗颗朝圣的心灵,每年穷游川藏线前往拉萨的驴友数以万计。 提起川藏线,我们不得不提到一个...
  • 得重新修建好路才能通。比如TCP的三次握手。但是非连接,比如UDP,双方可以随时断开连接,但是一旦另一方上线就又能收到对方的数据了。比如客户端因为某些原因(比如机器重启)断开了,服务端依然故我地等待接受数据...
  • 各位前辈,请问工程合同大包价是什么意思?是包死价吗?以下文字资料是由(历史新知网www.lishixinzhi.com)小编为大家搜集整理后发布的内容,让我们赶快一起来看一下吧!各位前辈,请问工程合同大包价是什么意思?是...
  • 过去东门外的渡口人特别多,经常有人掉到海河里,于是在此修建了浮桥,这座桥十分简陋,是用十三条木船连起来的,铺上木板后人打上面走。这地方人多是因为在河岸有大量存盐的盐坨,所以盐官厅也设在这里,盐关浮桥之...
  • 后面的意思是点1与点3的路已经建好, 在后面的就是点4 与点5 与点6之间连通。 代码如下: /* * g1.cpp * * Created on: 2015年3月10日 * Author: Administrator */ #include #include #include using ...
  • 我舅在建大,他家网络有毛病了,老是出现网络已经连接的提示,那是连接老掉线的意思。 昨天上门维修,起先判断是台式机网卡问题或其连接网线的问题导致手机也无法上网。因为拔掉台式机网后,手机一度可以正常上网。...
  • AE 修剪路径

    2022-05-15 02:35:09
    气泡动画开场 新建纯色 新建形状图层 添加-椭圆 添加-填充 添加-组 添加-组 把椭圆路径1和填充放进组 复制椭圆路径2 在复制的椭圆路径2中,修改大小,缩小 ...选中图层,选择关键帧辅助-序列
  • carve的意思

    2021-01-12 09:21:25
    1. 雕;刻 If you carve an object, you make it by cutting it out of a substance such as wood or stone. If you carve something such as wood or stone into an object, you... 将要修建两条三车道的公路穿过乡间。
  • 原标题:宇宙终极答案“42”到底是什么意思?超级计算机为我们揭晓答案42是一个简单的数字,看起来平平无奇。但是在一些科幻爱好者的眼里,42却代表着宇宙的终极答案。这到底是为什么呢?我们不得不从一部电影,...
  • 为什么4G、5G又称为蜂窝网络?跟蜂窝有什么关系?

    万次阅读 多人点赞 2020-03-20 09:01:43
    1.2 最短连线问题 要解释这个现象,首先我们先来思考这样一个数学问题: 有四座城市刚好分布在正方形的四个角,每条边距离100KM,城市分布如下图 由于城市的发展,需要在A、B、C、D四个城市之间修建马路,马路需要...
  • 会唱歌的路

    2021-12-11 00:23:18
    文| 贰沐编辑| 贰沐 子鱼会唱歌的路?...是什么意思?是说路会自己唱歌吗?开车行驶在普通的道路上,我们能够听到“嗡嗡”的各种杂乱无章的声音,而在有些特殊的路上,我们可以听到路面在发出有...
  • 这种情况下,你团队可能能够做点事儿,但一定是拖拖拉拉、懒懒散散地做事儿,精气神儿都会差点意思。 这有一层含义: 1)全力以赴去拼搏梦想,把每一次机会都当成最后一次,不留力气。 我告诉你一个事实,能用全力就...
  • 2、ArrayList中的功能函数 2.1 trimToSize()函数 该函数是将ArrayList实例的容量修建为列表实际的大小。 public void trimToSize() { modCount++; if (size ) { elementData = (size == 0) ? EMPTY_ELEMENTDATA : ...
  • 2019年总结:始不垂翅,终能奋翼

    千次阅读 2020-01-08 09:13:52
    在历史名城圣奥古斯丁走访17世纪西班牙殖民者修建的海滨军事要塞,凭吊沧海桑田的历史变迁。 在希尔顿黑德岛度假,享受无尽阳光与细腻如盐的白沙滩。 参访美国本土最南端的城市——佛罗里达州Key west岛...
  • 一、最初的三个基本信念 本次分享题目是《TiDB 的架构演进哲学》,既然讲哲学那肯定有故事和教训,否则哲学从哪儿来呢?但从另外的角度来说,一般大家来讲哲学就先得有信念。有一个内容特别扯的美剧叫做《美国众神...
  • 目录A : 元音跳跃B : 元音删除C : 公路修建D : 网络铺设思路 A : 元音跳跃 问题描述 现在有一个长度为 nn 的字符串,都有小写字母组成。 输出最长的连续元音的长度 输入格式 第一行一个整数 nn , 0\le n\le10^60≤n...
  • Hive涉及的知识点如下图所示,本文将逐一讲解:正文开始:一. Hive概览1.1 hive的简介Hive是基于Hadoop的一个数据仓库工具,可以将结构化的数据文件映射为一张数据库表,并...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,091
精华内容 836
热门标签
关键字:

修建的意思