当前位置:首页 » 《休闲阅读》 » 正文

F

4 人参与  2022年01月04日 10:35  分类 : 《休闲阅读》  评论

点击全文阅读


Powered by:NEFU AB-IN

F - 0-1 MST

  • 题意

    有一个菊花图,给出 n n n个点, m m m条边权为 1 1 1的边,其余的边边权为 0 0 0,问最小生成树的权值

  • 思路

    最优的情况是尽可能的多连边权为 0 0 0的边,即题目没有给出的边,那么连好了边权为 0 0 0的边,就会生成多个连通块,连通块之间的连边即是答案,所以答案就是补图的连通块数量-1

    实现的方法就是进行 d f s dfs dfs,每次进行 d f s dfs dfs找出现存顶点 u u u中不与该点相连的点,那么这些点就与 u u u在同一个连通块内,在总集合里删掉这些点,并且接着 d f s dfs dfs这些点

  • 代码

    /*
     * @Author: NEFU AB-IN
     * @Date: 2021-09-21 18:43:45
     * @FilePath: \ACM\CF\2021.9.17\e.cpp
     * @LastEditTime: 2021-09-21 19:49:56
     */
    #include <bits/stdc++.h>
    using namespace std;
    #define LL long long
    #define MP make_pair
    #define SZ(X) ((int)(X).size())
    #define IOS                      \
        ios::sync_with_stdio(false); \
        cin.tie(0);                  \
        cout.tie(0);
    #define DEBUG(X) cout << #X << ": " << X << endl;
    typedef pair<int, int> PII;
    
    const int N = 1e6 + 10;
    struct Edge
    {
        int v, ne;
    } e[N << 2];
    int h[N];
    int cnt;
    void add(int u, int v)
    {
        e[cnt].v = v;
        e[cnt].ne = h[u];
        h[u] = cnt++;
    }
    void init()
    {
        memset(h, -1, sizeof(h));
        cnt = 0;
    }
    set<int> s;
    
    void dfs(int u)
    {
        set<int> tmp = s;
        for (int i = h[u]; ~i; i = e[i].ne)
        {
            int to = e[i].v;
            tmp.erase(to);
        }
        for (auto i : tmp)
            s.erase(i);
        for (auto i : tmp)
            dfs(i);
    }
    
    signed main()
    {
        IOS;
        init();
        int n, m;
        cin >> n >> m;
        for (int i = 1; i <= m; ++i)
        {
            int u, v;
            cin >> u >> v;
            add(u, v);
            add(v, u);
        }
    
        int ans = 0;
        for (int i = 1; i <= n; ++i)
            s.insert(i);
        for (int i = 1; i <= n; ++i)
        {
            if (s.find(i) != s.end())
            {
                dfs(i);
                ans++;
            }
        }
        cout << ans - 1 << '\n';
        return 0;
    }
    

点击全文阅读


本文链接:http://zhangshiyu.com/post/32648.html

连通  给出  生成  
<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

最新文章

  • 她的记忆停留在了最爱初恋的那年许欣柔楚临川完本_她的记忆停留在了最爱初恋的那年(许欣柔楚临川)
  • 全书浏览假千金的实习生男友霸占我办公室,我反手让他们倾家荡产(顾家明)_假千金的实习生男友霸占我办公室,我反手让他们倾家荡产(顾家明)全书结局
  • 童养夫让我给他的新欢出修复费(林嘉芝林思雅)_童养夫让我给他的新欢出修复费林嘉芝林思雅
  • 全文资助生女婿让我给他白月光付三千万月子中心钱(宋清玉宋雅)列表_全文资助生女婿让我给他白月光付三千万月子中心钱
  • 碎在时光里的谎言喻景宴秦明月完本_碎在时光里的谎言(喻景宴秦明月)
  • 旧爱剜心吻成灰席鄢之岑秋全书免费旧爱剜心吻成灰席鄢之岑秋全书免费
  • 结婚六年丈夫不碰我谁知儿子亲爹是寡头(纪清言傅司砚),结婚六年丈夫不碰我谁知儿子亲爹是寡头
  • 老公想换掉我的男胎,我笑他自不量力(宋薇于继业)_老公想换掉我的男胎,我笑他自不量力宋薇于继业
  • 给太子下了噬心蛊后,皇后找上门(小夭赵劼)全书浏览_给太子下了噬心蛊后,皇后找上门全书浏览
  • 豪门绝嗣!带球跑的夫人回来了!(谢长宴慕清杳)_豪门绝嗣!带球跑的夫人回来了!谢长宴慕清杳
  • 完美身材(李朵林之晴)_完美身材李朵林之晴
  • 离婚后,我和快穿系统绑定(白意秋陈荣周立慧)_离婚后,我和快穿系统绑定(白意秋陈荣周立慧)

    关于我们 | 我要投稿 | 免责申明

    Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1