首页 > 代码库 > 完美网络 (优先队列)
完美网络 (优先队列)
完美网络
Time Limit: 1000MS Memory limit: 65536K
题目描述
完美网络是连通网络的基础上要求去掉网络上任意一条线路,网络仍然是连通网络。求一个连通网络要至少增加多少条边可以成为完美网络。
输入
第一行输入一个数T代表测试数据个数(T<=20)。每个测试数据第一行2个数n,m 分别代表网络基站数和基站间线路数。基站的序号为从1到n。接下来m行两个数代表x,y 代表基站x,y间有一条线路。
(0
输出
对于每个样例输出最少增加多少线路可以成为完美网络。每行输出一个结果。
示例输入
2 3 1 1 2 3 2 1 2 2 3
示例输出
2 1
提示
来源
中国海洋大学第三届“朗讯杯”编程比赛高级组试题
示例程序
思路:完美网络是连通网络的基础上要求去掉网络上任意一条线路,网络仍然是连通网络,这就要求每个点的入度要>=2。所以在输入u,v的时候每个点都要先加1,然后进行排序,将入度<2的压入优先队列,之后对优先队列进行操作,每次取出两个元素(因为一条路径有两个点),然后两个自加1,cnt也+1,然后讲入度小于2的继续压入优先队列中,直到就队列里剩下的点<2个。因为有1和0两种情况,所以要判断一下队列是否为空,当不为空是剩下的点肯定为1,要让他度为2,所以得加上1.最后输出cnt的值就行了ps:Orz陶神
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <algorithm> #include <iostream> #include <queue> using namespace std; struct cmp { bool operator()(const int &a,const int &b) { return a>b; } }; int sum[1000010]; int main() { int T; int n,m,i,j; int u,v; scanf("%d",&T); while(T--) { priority_queue<int ,vector<int >,cmp>q; memset(sum,0,sizeof(sum)); scanf("%d %d",&n,&m); for(i=1;i<=m;i++) { scanf("%d %d",&u,&v); sum[u]++; sum[v]++; } sort(sum+1,sum+n+1); //for(i=1;i<=n;i++) //printf("%d<<",sum[i]); for(j=1;j<=n;j++) { if(sum[j]<2) q.push(sum[j]); else break; } int a,b,cnt=0; while(q.size()>=2) { a=q.top(); q.pop(); b=q.top(); q.pop(); a+=1; b+=1; cnt++; if(a<2) q.push(a); if(b<2) q.push(b); } if(!q.empty()) { cnt=cnt+1; } printf("%d\n",cnt); } return 0; }
完美网络 (优先队列)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。