完美网络

忘是亡心i 2022-06-12 03:46 125阅读 0赞

Think:  
1知识点：优先队列  
2题意分析：去掉任意一条边，图仍是连通图，每个结点度数大于等于2

[建议参考博客1][1]  
[建议参考博客2][2]

[SDUT题目链接][SDUT]

以下为Accepted代码

#include <bits/stdc++.h>
    
    using namespace std;
    
    int deg[10004];
    
    int main(){
        int T, n, m, u, v, cnt, x, y;
        priority_queue<int> q;
        scanf("%d", &T);
        while(T--){
            scanf("%d %d", &n, &m);
            memset(deg, 0, sizeof(deg));
            for(int i = 1; i <= m; i++){
                scanf("%d %d", &u, &v);
                deg[u]++, deg[v]++;
            }
            while(!q.empty()){
                q.pop();
            }
            for(int i = 1; i <= n; i++){
                if(deg[i] < 2)
                    q.push(deg[i]);
            }
            cnt = 0;
            while(q.size() >= 2){
                x = q.top();
                q.pop();
                y = q.top();
                q.pop();
                x++, y++, cnt++;
                if(x < 2)
                    q.push(x);
                if(y < 2)
                    q.push(y);
            }
            if(q.size() > 0)
                cnt++;
            printf("%d\n", cnt);
        }
        return 0;
    }
    
    
    /***************************************************
    User name: 
    Result: Accepted
    Take time: 16ms
    Take Memory: 292KB
    Submit time: 2017-07-14 16:56:06
    ****************************************************/

[1]: http://blog.csdn.net/change_ac/article/details/47657453
[2]: http://blog.csdn.net/zhang_di233/article/details/47056331
[SDUT]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Index/problemdetail/pid/2506.html

发表评论取消回复

表情：

评论列表（有 0 条评论，125人围观）

还没有评论，来说两句吧...

相关阅读

相关网络运行 Android：实现移动设备与互联网的完美融合

网络运行 Android：实现移动设备与互联网的完美融合近年来，移动设备和互联网的普及和快速发展给人们的生活带来了巨大的改变。作为当前最主流和广泛使用的移动操作系统，And

我不是女神ヾ/ 2023年10月14日 22:46/ 0 赞/ 86 阅读

相关 SDUTACM 完美网络

题目描述完美网络是连通网络的基础上要求去掉网络上任意一条线路，网络仍然是连通网络。求一个连通网络要至少增加多少条边可以成为完美网络。输入第一行输入一个数T代

一时失言乱红尘/ 2022年09月25日 08:19/ 0 赞/ 144 阅读

相关完美网络

完美网络 Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^\_^ 题目描述完美网络是连通网络的基础上要求去掉

落日映苍穹つ/ 2022年08月10日 08:41/ 0 赞/ 125 阅读

相关完美字符串

约翰认为字符串的完美度等于它里面所有字母的完美度之和。每个字母的完美度可以由你来分配，不同字母的完美度不同，分别对应一个1-26之间的整数。约翰不在乎字母大小写。（也就是说

迷南。/ 2022年06月12日 06:44/ 0 赞/ 131 阅读

相关完美网络

Think: 1知识点：优先队列 2题意分析：去掉任意一条边，图仍是连通图，每个结点度数大于等于2 [建议参考博客1][1] [建议参考博客2][2] [SDU

忘是亡心i/ 2022年06月12日 03:46/ 0 赞/ 126 阅读

相关完美数

问题H：完美数时间限制：1秒内存限制：64 MB 提交：733解决：183 \[ [提交][Link 1] \] \[ [状态][Link 2] \] \[ [

悠悠/ 2022年05月22日 12:20/ 0 赞/ 232 阅读

相关完美网络

Problem Description 完美网络是连通网络的基础上要求去掉网络上任意一条线路，网络仍然是连通网络。求一个连通网络要至少增加多少条边可以成为完美网络。 Inp

╰半夏微凉°/ 2022年05月16日 08:37/ 0 赞/ 204 阅读

相关 SDN跟网络虚拟化的完美结合

SDN跟网络虚拟化的完美结合 ![SouthEast][] 之前说过，所谓的“SDN最适合的领域是数据中心”的说法，笔者认为更准确的说法应该是SDN最适合的领域是数据中

小咪咪/ 2022年03月28日 07:58/ 0 赞/ 234 阅读

相关完美数

计算前5个完美数完美数：完全数（Perfect number，又称完美数或完备数）是一些特殊的自然数。它所有的真因子（即除了自身以外的约数）的和（即因子函数），恰好等于它

左手的ㄟ右手/ 2022年01月23日 22:47/ 0 赞/ 239 阅读

相关 SDN跟网络虚拟化的完美结合

SDN跟网络虚拟化的完美结合 ![SouthEast][] 之前说过，所谓的“SDN最适合的领域是数据中心”的说法，笔者认为更准确的说法应该是SDN最适合的领域

「爱情、让人受尽委屈。」/ 2021年11月04日 22:54/ 0 赞/ 289 阅读