精华内容
下载资源
问答
  • 修建大桥

    2019-04-21 16:45:36
    小明来到一个由 n 个小岛组成的世界,岛与岛之间通过修建桥,来让岛上的居 民可以去其他的小岛。已知已经修建了 m 座桥,居民们想让小明帮忙计算,最 少还要在修建几座桥,居民们才能去所有的岛。  输入格式: 第一...

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

    1 题面

    公路修建

    2 分析

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

    3 具体实现

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

    解释一下变量的意思:
    pos代表从uuvv新加入的那个点
    vis[i]代表i是否在点集uu
    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;
    }
    
    
    展开全文
  • [ NOI 2011 ] 道路修建

    2018-09-20 20:03:00
    \(\\\) \(Description\) 一棵\(N\)个节点的树,每条边有边权,修建一条边的代价是: 这条边的边权\(\times\)修建好的树中,由该条边分开的两个子图节点数之差的绝对值 ...弃疗看讨论发现原来是说的这个意思...

    \(\\\)

    \(Description\)


    一棵\(N\)个节点的树,每条边有边权,修建一条边的代价是:

    这条边的边权\(\times\)修建好的树中,由该条边分开的两个子图节点数之差的绝对值

    求出修建整棵树的代价。

    • \(N\in [1,10^6]\)

    \(\\\)

    \(Solution\)


    被原题题面"建造方案有很多种 "干蒙...手玩样例玩不出来...弃疗看讨论发现原来是说的这个意思...

    一遍树形\(DP\)就好了,统计子树大小,分开的另一半的大小就是总点数\(-\)统计出的子树大小,直接累加答案。

    \(\\\)

    \(Code\)


    #include<cmath>
    #include<cstdio>
    #include<cctype>
    #include<cstdlib>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    #define N 1000010
    #define R register
    #define gc getchar
    using namespace std;
    typedef long long ll;
     
    inline int rd(){
      int x=0; bool f=0; char c=gc();
      while(!isdigit(c)){if(c=='-')f=1;c=gc();}
      while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc();}
      return f?-x:x;
    }
     
    ll ans;
    int n,m,tot,sz[N],hd[N];
    struct edge{int w,to,nxt;}e[N<<1];
    inline void add(int u,int v,int w){
      e[++tot].to=v; e[tot].w=w;
      e[tot].nxt=hd[u]; hd[u]=tot;
    }
     
    inline void dfs(int u,int fa){
      sz[u]=1;
      for(R int i=hd[u],v;i;i=e[i].nxt)
        if((v=e[i].to)!=fa){
          dfs(v,u); sz[u]+=sz[v];
          ans+=(ll)e[i].w*(ll)abs(n-(sz[v]<<1));
        }
    }
     
    int main(){
      n=rd();
      for(R int i=1,u,v,w;i<n;++i){
        u=rd(); v=rd(); w=rd();
        add(u,v,w); add(v,u,w);
      }
      dfs(1,0);
      printf("%lld\n",ans);
      return 0;
    }

    转载于:https://www.cnblogs.com/SGCollin/p/9683007.html

    展开全文
  • 这道题有一点点树上dp的意思(大佬轻喷 我刚拿到这道题的时候毫无头绪,只知道这道题要二分答案 为什么是二分答案??? 题目: 目前赛道修建的方案尚未确定。你的任务是设计一 种赛道修建的方案,使得修建的 m 条...

    这道题有一点点树上dp的意思(大佬轻喷

    我刚拿到这道题的时候毫无头绪,只知道这道题要二分答案

    为什么是二分答案???

    题目:

    目前赛道修建的方案尚未确定。你的任务是设计一
    种赛道修建的方案,使得修建的 m 条赛道中长度
    最小的赛道长度最大
    (即 m 条赛道中最短赛道的
    长度尽可能大)

    通常情况下出现 最小的……最大 或者 最大的……最小 时就是二分答案。

    如何二分答案???

    这道题问的是最小的长度最大, 那一定是
    二分长度, 即我们可以先设开始时

    l = 0, r = 最大值  mid = (l + r) / 2

    我们求出的每一条长度大于等于mid的赛道我们称之为合法, 如果合法的赛道数大于m, 那么说明mid <= 真实答案, 所以我们就让 l = mid + 1,继续二分, 否则就让 r = mid。

    如何转移???

    其实刚开始瞎做的时候我并没有发现这是个树上dp(逃

    72990.png

    有这么一个图,我们先从每个子树考虑

    72991.png

    我们假设, 2这个节点为根的子树中,从5到2再到7的这条路径是满足条件的合法赛道,那么我们可以直接答案加1, 然后把这两条边删去。

    那么可能会剩下几条边。

    我们可以发现, 如果要用2这个节点去构成长度合法的赛道, 要么是2节点开始从0往上走,去凑出合法长度, 要么是挑一个2下面的边(我们先假设为6到2这条边)往上去凑, 最多只能挑一条的边,那么我们一定是要挑一条没用过的最长的边。

    n = 50000, 我们可以用multiset的lower_bound来实现每个节点的边的有序和查找某条边是否可以凑成合法的边。

    这可以这么实现

    int dfs(int x, int fa, int mid) {
        int len = 0;
        multiset<int> s;
        for (int i = p[x]; i != -1; i = e[i].nxt) {
            int v = e[i].v, w = e[i].w, l;
            if (v == fa) {
                continue;
            }
            l = dfs(v, x, mid) + w;
            opt[x] += opt[v];
            if (l >= mid) {
                opt[x]++;
            } else {
                s.insert(l);
            }
        }
        while (!s.empty()) {
            int now = (*s.begin());
            s.erase(s.begin());
            multiset<int>::iterator it = s.lower_bound(mid - now);
            if (it != s.end()) {
                s.erase(it);
                opt[x]++;
            } else {
                len = now;
            }
        }
        return len;
    }

    至于菊花图的话可能会被卡???我没试过,如果担心的话可以特判一下,只需要一次排序然后lower_bound就OK了。

    8.19更新

    有同学不知道菊花图是什么
    73248.png
    就是介个东西QWQ

    菊花图通常会被卡,所以需要特判或者寻找更高效算法( 一般是特判辣, 因为菊花图上的问题大部分比较简单的 )

    好像也没多少树上dp

    转载于:https://www.cnblogs.com/with6676/p/11517825.html

    展开全文
  • 最小堆dijkstra算法解ccf-csp的地铁修建问题
  • 我舅在建大,他家网络有毛病了,老是出现网络已经连接的提示,那是连接老掉线的意思。 昨天上门维修,起先判断是台式机网卡问题或其连接网线的问题导致手机也无法上网。因为拔掉台式机网后,手机一度可以正常上网。...
  • 这句话的意思就是树上的任意一个节点它的儿子最多两个,这意味着什么? (不知道) 我们分析一下性质,对于一棵树中的任意一个节点(把个体先分析)我们可以知道抠链要么是直接在内部两个儿子通过父亲相连拼接成一...
  • 后面的意思是点1与点3的路已经建好, 在后面的就是点4 与点5 与点6之间连通。 代码如下: /* * g1.cpp * * Created on: 2015年3月10日 * Author: Administrator */ #include #include #include using ...
  • 1951年开始修建雅安至拉萨的康藏公路。西康撤省后两条路并称川藏公路。川藏线以其特有的魅力,虽遗世而独立,却吸引着一颗颗朝圣的心灵,每年穷游川藏线前往拉萨的驴友数以万计。 提起川藏线,我们不得不提到一个...
  • 过去东门外的渡口人特别多,经常有人掉到海河里,于是在此修建了浮桥,这座桥十分简陋,是用十三条木船连起来的,铺上木板后人打上面走。这地方人多是因为在河岸有大量存盐的盐坨,所以盐官厅也设在这里,盐关浮桥之...
  • 30多年来那些汉奸文人总是把甲午战争失败的原因,归结为是慈禧太后挪用海军军费修建颐和园。据史料记载,慈禧太后连续几年挪用的军费总额,只能购买两艘战舰。如果说慈禧太后挥霍了两艘战舰,就要承担国家败亡的责任...
  • 随后的 N(N-1)/2 行对应村庄间道路的成本及修建状态,每行给4个正整数,分别是两个村庄的编号(从1编号到N),此两村庄间道路的成本,以及修建状态:1表示已建,0表示未建。 <br>当N为0时输入结束。   Output 每...
  • 原标题:宇宙终极答案“42”到底是什么意思?超级计算机为我们揭晓答案42是一个简单的数字,看起来平平无奇。但是在一些科幻爱好者的眼里,42却代表着宇宙的终极答案。这到底是为什么呢?我们不得不从一部电影,...
  • 地球经过了1000万年的计算后,就在要得出结论的前5分钟,却被另一个超级文明Vogons毁灭了,因为地球挡住了他们要修建的星际高速公路。 《银河系漫游指南》是如此有名,以至于连42这个数字在科幻迷眼里都具有了非凡...
  • 图结构练习——最小生成树

    千次阅读 2014-10-17 18:00:56
     有n个城市,其中有些城市之间可以修建公路,修建不同的公路费用是不同的。现在我们想知道,最少花多少钱修公路可以将所有的城市连在一起,使在任意一城市出发,可以到达其他任意的城市。   输入  输入...
  • 程序员的十年之痒

    万次阅读 多人点赞 2020-11-09 08:27:52
    那时候在读高中二年级,那个中午刚走到学校大门外,阳光正好通过那个传单刺到了我的眼睛,传单的内容很长,是一个技术学院为了招生写的关于黑客的描述,大概意思是那是热爱自由、平等、开源,躲在黑暗角落的怪人。...
  • 剪枝论文总结(二)

    2020-11-23 09:02:44
    过滤器修建的研究可以主要分为两类:逐层修建和全局修建。由于每层网络需要预定义修建率,对于深度卷积,逐层修剪会非常耗时。全局修建只需要个一个修建率就可以对整个网络结构进行修改,但是全局修剪必须解决全局...
  • 谈古论津丨西沽公园

    2019-02-11 00:40:05
    天津为退海之地,意思就是海面下降或者陆地上升形成的地理环境,现在塘沽、汉沽还有盐场,就在一定程度上说明了这一点。因此天津地势低洼,沽坑相连,素有七十二沽之说,所以天津的地名带“沽”字的也特别多,像什么...
  • spaceclaim脚本(线生成面体)

    千次阅读 2019-10-01 05:40:42
    #新建一个列表,用来保存修剪曲线(PS:修建曲线的意思是开始点和结束点不在一起,圆就不属于修建曲线) #注意和Line,Circle类型等的区别 curves = List[ITrimmedCurve]() curveSegment =CurveSegment.Create(Point....
  • 红灯和围墙--立交桥(续)

    千次阅读 2010-02-09 22:19:00
    很多人都知道linux比windows更稳定,更安全,可是身为inux迷的我却不这么认为,当然我的意思并不是说linux没有windows安全,它们都有漏 洞,都不安全,说linux更安全的原因是因为linux的用户比较少,黑客们认为攻击...
  • 过些时候,四个孩子中的两个小的,16岁的吉米和13岁的埃米莉,会帮着我一起把拖了很久没修的室外厕所修葺一下,那是专为室外干活修建的。这个月晚些时候,我们要给果树喷洒药水,要油漆谷仓,要给菜园播种,要赶在新...
  • 本文主要针对SSD的tensorflow框架下的实现的源码解读即对网络模型的理解。 【前言】 首先在github上下载tensorflow版的... 同时附上论文地址:SSD 论文下载 解压SSD-Tensorflow-master.zip 到自己工作目录下。...S...
  • 答案:at the side of Solomon’s head。因为Solomon是古代以色列的一个国王,他在耶路撒冷修建了一座著名的庙宇。Temple是庙宇的意思,但还有另外的一个意思是头部的侧面,即每只耳朵的前上方。
  • 1.2 最短连线问题 要解释这个现象,首先我们先来思考这样一个数学问题: 有四座城市刚好分布在正方形的四个角,每条边距离100KM,城市分布如下图 由于城市的发展,需要在A、B、C、D四个城市之间修建马路,马路需要...
  • 点击上方 "云祁QI"关注,星标或置顶一起成长如今,随着诸如互联网以及物联网等技术的不断发展,越来越多的数据被生产出来。据统计,每天大约有超过2.5亿亿字节的各种各样数据...
  • 题意是在n个餐厅之间选择k个地方修建...状态转移方程式的意思是:到达j的时候区间(i,j)上所拥有的最小的值。到达j的时候可以选择j位置上不修建仓库dp[i][j] = dp[i][j]。或者选择修仓库那么之前已经有i-1个仓库修建
  • 2、ArrayList中的功能函数 2.1 trimToSize()函数 该函数是将ArrayList实例的容量修建为列表实际的大小。 public void trimToSize() { modCount++; if (size ) { elementData = (size == 0) ? EMPTY_ELEMENTDATA : ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,897
精华内容 758
关键字:

修建的意思