Friendships

Friendships

题意：构造一个有n个节点的无向图，规定任意边为1，要求有k对（i,j）i<j的边距离至少为2

思路：k最多有（n-1)*(n-2)/2,先从1开始连接所有节点，再从2开始，再。。。直到有k对.

#include<bits/stdc++.h>
using namespace std;
int mp[105][105];
int main(){
	int n,k;
	cin>>n>>k;
	int mx=(n-1)*(n-2)/2;
	if(mx<k){
		puts("-1");
		return 0;
	}
	int cnt=0;
	memset(mp,0,sizeof(mp));
	for(int i=2;i<=n;i++)
		mp[1][i]=mp[i][1]=1;
	for(int i=2;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			if(!mp[i][j]&&mx>k)
				mp[i][j]=mp[j][i]=1,--mx;
		}
	}
	for(int i=1;i<=n;i++)
		for(int j=i+1;j<=n;j++)
			cnt+=mp[i][j];
	printf("%d\n",cnt);
	for(int i=1;i<=n;i++)
		for(int j=i+1;j<=n;j++)
			if(mp[i][j])
				printf("%d %d\n",i,j);
}