自动搬运

查看原文

来自洛谷，原作者为

	AnteAntibe Moonlight illuminate me, Promise is coming true.

搬运于2025-08-24 22:26:32，当前版本为作者最后更新于2025-04-18 21:02:18，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

一个晚上，我打开了这道题……
思考良久无果，打开题解。发现题解居然没有讲述具体的思路？？无奈继续思考……

于是就有了这篇题解。

Description

首先读题。

我们可以将每一个学生抽象为一个点，于是答案就变成了一张图。注意到有“如果 A 认为 B 是他的朋友，那么 B 也认为 A 是他的朋友”一句话，因此图中的连边是双向边。

现在分别规定每个男、女连向同性、异性的边数，我们要做的就是构造出一个满足该条件的图。同时我们需要最小化点的边数。

Solution

乍一看好像很没有头绪？ 于是手玩一下样例。

图长这样。

相信大家在画这个图的时候多少注意到：和同性连边、和异性连边是相互独立的两个过程。因为很显然，并不存在一个点即是女生又是男生。于是合法的点数只需要同时满足连得出同性、异性的条件即可。

先考虑异性。每个女性都拉出 $b$ 条边，那么总边数一定是 $b$ 的倍数，同理它也得是 $c$ 的倍数。于是我们可以很轻松的得到：

换句话说：

接着考虑同性。看起来很简单：以女性举例，只需要有 $a$ 个人给这个点连线即可。样例好像可以跑对，但是实际上这个做法是存在问题的。

同样先以女性举例：同性的好友关系一共 $m \times a$ 条，由于是双向边，所以边数共有 $\frac{m \times a}{2}$ 条。

发现问题了吗？如果 $m$ 与 $a$ 同为奇数，那么计算出的边数就不是一个整数。显然“连了半条边”这件事是不行的。$n$ 与 $b$ 的关系同理。于是同性间连边需要满足：

• $m > a$ 并且 $n > d$。
• $m$ 与 $a$ 至少有一个为偶数，$n$ 与 $d$ 至少有一个为偶数。

求出满足如上条件的最小点数即可满足第一问。

现在问题只剩如何建边。只需要满足每个点连向异性、同性的边数没问题，那这个图怎么建都是对的。同时这题甚至没给数据范围，更不可能在复杂度上卡你，暴力建边即可。

我的做法是开个优先队列存一个点还有几条边没连，这样逻辑比较简单，只需要取队头一个点然后挨个连边连完就好了。应该有别的方法，不过我没试过。

程序：

#include<bits/stdc++.h>
#define mkp make_pair 
#define pii pair<int ,int>
using namespace std;

int a ,b ,c ,d ,tmp1 ,tmp2 ,m ,n;

priority_queue<pair<int ,int> > q1 ,q2 ,q3 ,q4;

int main() {
	scanf("%d %d %d %d" ,&a ,&b ,&c ,&d);
	int tmp = __gcd(b ,c);
	tmp1 = c / tmp;
	tmp2 = b / tmp;
	m = c;
	n = b;
	for (; ;) {
		bool j1 = (m > a && n > d);
		bool j2 = (m % 2 != 1 || a % 2 != 1);
		bool j3 = (n % 2 != 1 || d % 2 != 1);
		if ((j1 && j2) && (j3 && j2)) {
			break;
		}
		m += tmp1;
		n += tmp2;	
	}
	printf("%d %d\n" ,m ,n);

    for (int i=1 ;i<=m ;i++) {
		q1.push(mkp(a ,i));
	}
	for (;q1.size();) {
		pii u = q1.top();
		q1.pop();
		for (;u.first > 0;) {
			u.first --;
			pii v = q1.top();
			v.first--;
			q1.pop();
			q1.push(v);
			printf("%d %d\n" ,u.second ,v.second);
		}
	}
	
	for (int i=1 ;i<=n ;i++) {
		q2.push(mkp(d ,m + i));
	}
	for (;q2.size();) {
		pii u = q2.top();
		q2.pop();
		for (;u.first > 0;) {
			u.first --;
			pii v = q2.top();
			v.first--;
			q2.pop();
			q2.push(v);
			printf("%d %d\n" ,u.second ,v.second);
		}
	}
	
	for (int i=1 ;i<=m ;i++) {
		q3.push(mkp(b ,i));
	}
	for (int i=1 ;i<=n ;i++) {
		q4.push(mkp(c ,m+i));
	}
	for(;q3.size();) {
		pii u = q3.top();
		q3.pop();
		for (;u.first > 0;) {
			u.first--;
			pii v = q4.top();
			v.first --;
			q4.pop();
			if (v.first > 0) {
				q4.push(v);
			}
			printf("%d %d\n" ,u.second ,v.second);
		}
	}
	
	return 0;
}

坑点还是有些的。注意取等条件。还有就是搞清楚六个字母分别代表什么，题目描述中的变量含义有一些反直觉。