Codeforces Gym 100269K Kids in a Friendly Class 构造题
Kids in a Friendly Class
题目连接:
http://codeforces.com/gym/100269/attachments
Description
Kevin resembles his class in primary school. There were girls and boys in his class. Some of them were
friends, some were not. But if one person considered another person a friend, the opposite was also true.
Interestingly, every girl had exactly a friends among girls and exactly b friends among boys, whereas
every boy had exactly c friends among girls and exactly d friends among boys.
Kevin does not remember the size of his class. Help him reconstruct the class with minimal possible
number of kids, such that the above conditions are satisfied.
Input
The only line contains four integers a, b, c, and d (1 ≤ a, b, c, d ≤ 50)
Output
Output an example of a class of minimal possible size satisfying the above conditions.
The first line should contains two positive integers: m — the number of girls, and n — the number of
boys.
Let’s assign numbers 1 through m to the girls and m + 1 through m + n to the boys.
Each of the next lines should contain a pair of distinct integers describing a pair of friends by their
numbers. Each pair of friends should appear exactly once in this list.
Sample Input
1 2 1 2
Sample Output
2 4
1 2
1 3
1 5
2 4
2 6
3 4
3 5
4 6
5 6
Hint
题意
每个女生认识a个女生,b个男生
每个男生认识c个女生,d个男生
问你怎么构图,才能使得男生+女生最少
题解:
首先我们假设知道了男生和女生的数量的话
建边就很简单,贪心去建边就好了,每次连接度数最小的点
至于怎么知道男生和女生的数量呢?
首先男生和女生的数量肯定是lcm(b,c)的倍数
然后不断check就好了
check主要只判断同性之间就好了
每条边必须连接两个点之内的check一下就好了
有个定理叫做Havel-Hakimi定理
代码
#include<bits/stdc++.h>
using namespace std;
int gcd(int a,int b)
{
if(b==0)return a;
return gcd(b,a%b);
}
int a,b,c,d;
bool check(int n,int m)
{
if(b>m)return false;
if(c>n)return false;
if(a>=n)return false;
if(d>=m)return false;
if(n%a!=0)return false;
if(m%b!=0)return false;
return true;
}
void getedge(int n,int m)
{
priority_queue<pair<int,int> >Q;
for(int i=1;i<=n;i++)
Q.push(make_pair(a,i));
while(!Q.empty())
{
pair<int,int> now = Q.top();
Q.pop();
for(int i=0;i<now.first;i++)
{
pair<int,int> next = Q.top();
Q.pop();
printf("%d %d\n",now.second,next.second);
next.first--;
Q.push(next);
}
}
for(int i=n+1;i<=n+m;i++)
Q.push(make_pair(d,i));
while(!Q.empty())
{
pair<int,int> now = Q.top();
Q.pop();
for(int i=0;i<now.first;i++)
{
pair<int,int> next = Q.top();
Q.pop();
printf("%d %d\n",now.second,next.second);
next.first--;
Q.push(next);
}
}
priority_queue<pair<int,int> >Q1;
priority_queue<pair<int,int> >Q2;
for(int i=1;i<=n;i++)
Q1.push(make_pair(b,i));
for(int i=n+1;i<=m+n;i++)
Q2.push(make_pair(c,i));
while(!Q1.empty())
{
pair<int,int> now = Q1.top();
Q1.pop();
for(int i=0;i<now.first;i++)
{
pair<int,int> next = Q2.top();
Q2.pop();
printf("%d %d\n",now.second,next.second);
next.first--;
if(next.first!=0)Q2.push(next);
}
}
}
int main()
{
freopen("kids.in","r",stdin);
freopen("kids.out","w",stdout);
scanf("%d%d%d%d",&a,&b,&c,&d);
int t=gcd(b,c);
int x=b/t,y=c/t;
int n,m;
for(n=b,m=c;n<=d||m<=a||(m&1)&&(a&1)||(n&1)&&(d&1);n+=x,m+=y);
swap(n,m);
cout<<n<<" "<<m<<endl;
getedge(n,m);
}
最新文章
- armv7 armv7s arm64
- tomcat下运行多个项目
- Uva1515 Pool construction
- iOS 关于iphone6 和 iphone6 plus 的适配
- javascript_获取浏览器属性
- laravel 重写以及500错误
- java.util.regex.PatternSyntaxException: Unexpected internal error near index 1 \ ^
- poj 2886Who Gets the Most Candies?
- 【CDOJ931】Car race game(树状数组求逆序)
- [Oracle] Insert All神奇
- 微信小程序之两个页面传值
- day15-ajax和jquery
- python 全栈开发,Day111(客户管理之 编辑权限(二),Django表单集合Formset,ORM之limit_choices_to,构造家族结构)
- ubuntu 安装(install) pwntcha[一个做";验证码识别";的开源程序]
- $.post 和 $.get 设置同步和异步请求
- [ASP.NET]HttpCookieCollection to CookieCollection的最简单方法
- Activiti工作流引擎简介
- 以打字形式展示placeholder的插件
- js-jquery-002-条形码-一维码
- ipt_connlimit限制并发,ipt_recent限制单位时间内的请求数目