简单的二分图

一：什么是二分图？二分图是神魔？可以二分查找吗

就是顶点集V可分割为两个互不相交的子集，并且图中每条边依附的两个顶点都分属于这两个互不相交的子集，两个子集内的顶点不相邻。——百度百科

二：为什么他是二分图？你说是就是？

我们可以看出，由于子集中每个顶点之间都没有路径，故任选包含两个子集中元素的连通图合法

三：具体做法不愿看我哔哔的直接去看代码


从上图可以看出，当顶点数量为偶数时，路径最多 n^2/4 条

从上图可以看出，当顶点数量为奇数时，路径最多 n/2*(n/2+1) 条

再通过一个简单的枚举输出，便AC了

四：代码你们最期待的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int main()
{
	cin>>n;
	if(n%2==0)
	{
		cout<<n*n/4<<endl;
	}
	else 
	{
		cout<<(n/2)*(n/2+1)<<endl;
	}
	for(int i=1;i<=n/2;i++)
	for(int l=n/2+1;l<=n;l++)
	cout<<i<<' '<<l<<endl;
	return 0;
}