首页 > 代码库 > 完美网络（优先队列实现）
完美网络（优先队列实现）
完美网络
Time Limit: 1000MS Memory limit: 65536K
题目描述
完美网络是连通网络的基础上要求去掉网络上任意一条线路，网络仍然是连通网络。求一个连通网络要至少增加多少条边可以成为完美网络。
输入
第一行输入一个数T代表测试数据个数（T<=20）。每个测试数据第一行2个数n,m 分别代表网络基站数和基站间线路数。基站的序号为从1到n。接下来m行两个数代表x,y 代表基站x,y间有一条线路。
(0
输出
对于每个样例输出最少增加多少线路可以成为完美网络。每行输出一个结果。
示例输入
23 11 23 21 22 3
示例输出
21
完美网络，只有图中每个点的度>=2，此时才能保证任意删去一条边，图还是联通。
1 #include<iostream> 2 #include<algorithm> 3 #include<stdio.h> 4 #include<string.h> 5 #include<queue> 6 using namespace std; 7 8 int n,m; 9 int dg[10000100];//点的度10 int main()11 {12 int T;13 scanf("%d",&T);14 while(T--)15 {16 priority_queue<int, vector<int>, greater<int> >que;//定义优先队列17 memset(dg,0,sizeof(dg));18 scanf("%d %d", &n,&m);19 int x,y;20 for(int i=0;i<m;i++)21 {22 scanf("%d%d",&x,&y);23 dg[x-1]++;//输入一条边，同时使两顶点度加124 dg[y-1]++;25 }26 sort(dg,dg+n);//排序，从小到大27 28 for(int i=0;i<n;i++)29 {30 if(dg[i]<2)//把度小于2的点压入优先队列31 que.push(dg[i]);32 }33 int cnt = 0;//需要加的边数34 while(que.size()>=2)35 {36 int t = 0,f = 0;37 t = que.top();38 que.pop();39 40 f = que.top();41 que.pop();42 43 ++t;//取出栈顶的两个元素，度分别加1,44 ++f;45 cnt++;//这样相当于加了一条边46 if(t<2)//如果度加完后还是小于2，则下回优先考虑。47 que.push(t); //放入优先队列48 if(f<2)49 que.push(f);50 }51 if(!que.empty())//如果执行完上述while循环后，队列还不为空52 { //则这种情况只能说明，队列里还剩下一个元素，他的度仍小于2.53 cnt = cnt + 1;54 }55 printf("%d\n", cnt);56 }57 return 0;58 }
完美网络（优先队列实现）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。