P7089 [NWRRC 2013] Kids in a Friendly Class 题解

· · 题解

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

于是就有了这篇题解。

Description

首先读题。

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

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

Solution

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

图长这样。

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

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

m \times b = n \times c

换句话说：

\frac{c}{b} = \frac{m}{n}

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

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

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

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

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

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

程序：

#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;
}

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