bzoj2162: 男生女生 | jeffswt: the ac moments

Description

雨荨的班主任安远老师是一个非常严厉的老师. 到了大学, 男生和女生之间难免会出现一些暧昧关系, 但这样显然是影响学习的. 所以作为艾利斯顿的一块招牌, 安远老师当然要拒绝这种现象的出现以及繁衍. 所以每当安远老师发现一个男生和一个女生放学走在一起或者男女生之间互相传纸条等, 他就会立马制止并且通知家长. 他也要求所有男女生晚上八点之后必须关手机, 并且不定期打电话检查. 于是安远老师的学生都感慨: 这货不是大学, 不是大学. 安远老师的学生里, 一共有 \(n\) 个男生和 \(n\) 个女生, 编号都以\(1-n\) 编号. 有 \(m\) 对男女生之间有暧昧关系.

现在安远老师想找出这样一个男女生群体, 每个男生都和每个女生之间有暧昧关系, 并且男女生总数最大. 注意, 男生数目或者女生数目可以为 \(0\). 如果有多个这样的群体, 安远老师会选择男生最多的那个群体, 因为他觉得男生会很不安分. 如果这样的群体依然不唯一, 他会选择任意一个. 接下来, 安远老师从选出的这个群体的所有暧昧关系中, 选出 \(k\) 个进行调查, 使得这个群体的所有男生和女生, 都至少和其中的一对暧昧关系有关系 (即是这个暧昧关系的男/女主人公). 安远老师想让你告诉他, 总方案数除以 \(19921228\) 的余数是多少.

Input

输入的第一行包含两个正整数 \(n\) 和 \(k\), 分别代表男生女生的个数, 以及安远老师要选择的暧昧关系个数.

第二行为一个正整数 \(m\), 代表暧昧关系总个数. 接下来 \(m\) 行, 每行两个整数, 代表一对有暧昧关系的男女生编号.

Output

第一行有两个空格隔开的整数, 代表选择的团体内男生和女生的个数. 第二行有一个整数, 代表选法除以 \(19921228\) 的余数.

Sample Input

Sample Output

2 2
2

Data Range

对于 100% 的数据, 满足:\(n \leq 50, m, k \leq 2500\)

同一对暧昧关系不会在输入中出现多次.

Explanation

首先我们来解决如何求值的问题.

如果选出来的每一个学生都至少和其中一对暧昧关系有关系, 那么也就是说, 我们不能选择任何一位不和任何暧昧关系有关系的学生......

所以对于任意两个学生 (当然是男女生...... ) , 如果他们之间没有暧昧关系, 则连一条边. 对于这个二分图建图, 跑一遍最小割.

考虑到安远老师对男生的报道存在偏差, 我们需要给男生增加权值, 以使得选中人数同样多时, 男生更优先被选到.

这样我们就求得了总的数量, 现在考虑方案数.

现在考虑被选中的男生的数量为 \(a\), 女生为 \(b\), 则根据容斥原理, 我们有:\[ ans = \sum_{i=0}^{a} \sum_{j=0}^{b} C_a^i \cdot C_b^j \cdot C_k^{ij} \cdot (1\ \text{if}\ a + b \equiv i + j\ \text{else}\ -1) \] 最后不要忘记取一个模......

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <cstring>

using namespace std;
typedef long long lli;
const int maxn = 2510, maxm = 200100, maxN = 100;
const lli infinit = 0x007f7f7f7f7f7f7fll;
const int modr = 19921228;

class Dinic
{
public:
    struct edge
    {
        int u, v;
        lli flow;
        edge *next, *rev;
    };
    int n, s, t, ecnt;
    edge *edges[maxn], epool[maxm];
    int level[maxn];
    void add_edge(int u, int v, lli flow)
    {
        edge *p = &epool[++ecnt],
             *q = &epool[++ecnt];
        p->u = u; p->v = v; p->flow = flow;
        p->next = edges[u]; edges[u] = p; p->rev = q;
        q->u = v; q->v = u; q->flow = 0;
        q->next = edges[v]; edges[v] = q; q->rev = p;
        return ;
    }
    bool make_level(void)
    {
        queue<int> que;
        memset(level, 0, sizeof(level));
        level[s] = 1;
        que.push(s);
        while (!que.empty()) {
            int p = que.front();
            que.pop();
            for (edge *ep = edges[p]; ep; ep = ep->next)
                if (ep->flow && !level[ep->v]) {
                    level[ep->v] = level[p] + 1;
                    que.push(ep->v);
                }
        }
        if (level[t] <= 0)
            return false;
        return true;
    }
    lli find(int p, lli mn)
    {
        if (p == t)
            return mn;
        lli sum = 0, tmp;
        for (edge *ep = edges[p]; sum < mn && ep; ep = ep->next)
            if (ep->flow && level[ep->v] == level[p] + 1) {
                tmp = find(ep->v, min(mn - sum, ep->flow));
                if (tmp > 0) {
                    sum += tmp;
                    ep->flow -= tmp;
                    ep->rev->flow += tmp;
                }
            }
        if (sum <= 0)
            level[p] = 0;
        return sum;
    }
    lli eval(void)
    {
        lli sum = 0, tmp;
        while (make_level()) {
            tmp = find(s, infinit);
            if (tmp <= 0)
                break;
            sum += tmp;
        }
        return sum;
    }
} graph;

int n, K, m;
bool mp[maxN][maxN];
lli C[maxn][maxn];

int main(int argc, char** argv)
{
    scanf("%d%d%d", &n, &K, &m);
    for (int i = 1, a, b; i <= m; i++) {
        scanf("%d%d", &a, &b);
        mp[a][b] = true;
    }
    // Constructing graph
    graph.n = n*2 + 2;
    graph.s = graph.n - 1;
    graph.t = graph.n;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (!mp[i][j])
                graph.add_edge(i, j + n, infinit); // Don't cut!
    for (int i = 1; i <= n; i++)
        graph.add_edge(graph.s, i, 1000), // Male first, using a higher rank
        graph.add_edge(i + n, graph.t, 999);
    // Running flow, and evaluating the rest
    int flow = graph.eval();
    int tmp = (int)(flow / 1000 + 1) * 1000;
    int res_m = 0, res_f = 0;
    res_f = (tmp - flow) % 1000;
    flow -= res_f * 999;
    res_m = flow / 1000;
    res_f = n - res_f, res_m = n - res_m;
    // First batch of results
    printf("%d %d\n", res_m, res_f);
    // Tending to get the... combinations
    // Using Yang Hui triangles, again.
    C[0][0] = 1;
    for (int i = 1; i <= 2501; i++) {
        C[i][0] = 1;
        for (int j = 1; j <= i; j++) {
            C[i][j] = C[i-1][j] + C[i-1][j-1];
            while (C[i][j] >= modr)
                C[i][j] -= modr;
        }
    }
    // Get the count of ways to...
    int res = 0;
    for (int i = 0; i <= res_m; i++)
        for (int j = 0; j <= res_f; j++) {
            int flag = (res_m + res_f) ^ (i + j);
            int tmp = 1ll * C[res_m][i] * C[res_f][j] % modr * C[i*j][K] % modr;
            res += tmp * (flag & 1 ? -1 : 1);
            res = (res % modr + modr) % modr;
        }
    printf("%d\n", res);
    return 0;
}