SDUTACM 完美网络

一时失言乱红尘 2022-09-25 08:19 113阅读 0赞

## 题目描述 ##

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

## 输入 ##

第一行输入一个数T代表测试数据个数（T<=20）。每个测试数据第一行2个数n,m 分别代表网络基站数和基站间线路数。基站的序号为从1到n。接下来m行两个数代表x,y 代表基站x,y间有一条线路。

( 0 < n < m < 10000)

## 输出 ##

对于每个样例输出最少增加多少线路可以成为完美网络。每行输出一个结果。

## 示例输入 ##

2
    3 1
    1 2
    3 2
    1 2
    2 3

## 示例输出 ##

2
    1

## 提示 ##

#include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    #include<queue>

#include <algorithm>

using namespace std;

int main()

{
    	int t,i,n,m,a,b,sum,d[10000];
    	scanf("%d",&t);
    	while(t--)
    	{
    		sum=0;
    		memset(d,0,sizeof(d));
    		priority_queue<int,vector<int>, greater<int> >p;//优先队列
                    scanf("%d%d",&n,&m);
    		for(i=0;i<m;i++)
    		{
    			scanf("%d%d",&a,&b);
    			d[a]++;
    			d[b]++;
    		}
    		sort(d+1,d+n+1);//对度数排序
    		for(i=1;i<=n;i++)
    		{
    			if(d[i]<2)
                                    p.push(d[i]);
    			else 
    				break;
    		}
    		while(p.size()>=2)
    		{
    			a=p.top();
                            p.pop();
    			b=p.top();
    			p.pop();
    			a++;
    			b++;
    			sum++;
    			if(a<2)
    				p.push(a);
    			if(b<2)
    				p.push(b);
    		}
    		if(!p.empty())
    			sum++;
    		printf("%d\n",sum);
    	}
    	return 0;
    }

发表评论取消回复

表情：

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

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

相关阅读

相关 SDUTACM 完美网络

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

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

相关 SDUTACM成绩评估

题目描述我们知道，高中会考是按等级来的。 90—100为A; 80—89为B; 70—79为C; 60—69为D; 0—59为E。

冷不防/ 2022年09月22日 11:37/ 0 赞/ 123 阅读

相关 SDUTACM素数判定

题目描述对于表达式n 2\+n+41，当n在（x,y）范围内取整数值时（包括x,y）(-39<=x,y<=50)，判定该表达式的值是否都为素数。输入输入数据

阳光穿透心脏的1/2处/ 2022年09月22日 03:57/ 0 赞/ 170 阅读

相关 SDUTACM图形打印

题目描述请打印如下图形，要求输入n的值，按照图形中字母排列规则打印出相关图形。 ![1292.jpg][] 　　　　　　　　　　　　　输入输入整数n(1≤n

Bertha 。/ 2022年09月22日 03:57/ 0 赞/ 181 阅读

相关 SDUTACM多项式求和

题目描述多项式的描述如下： 1 - 1/2 + 1/3 - 1/4 + 1/5 - 1/6 + ... 现在请你求出该多项式的前n项的和。输入输入数

你的名字/ 2022年09月22日 01:27/ 0 赞/ 128 阅读

相关 SDUTACM图案打印

题目描述一年一度的植树节就要到了，计算机学院学生准备在学院教学楼门前的空地上种植树木。为使树木排列得更加美观，大家决定把树木排列成菱形。现在告诉你我们所拥有的树木能排列

た入场券/ 2022年09月21日 04:57/ 0 赞/ 170 阅读

相关完美网络

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

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

相关 SDUTACM 双向队列

题目描述想想双向链表……双向队列的定义差不多，也就是说一个队列的队尾同时也是队首；两头都可以做出队，入队的操作。现在给你一系列的操作，请输出最后队列的状态；

本是古典何须时尚/ 2022年07月17日 01:41/ 0 赞/ 133 阅读

相关完美网络

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

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

相关完美网络

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

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