[CODEVS 1301] 任务分配

描述

有N位工作人员，同时有N项任务, 每人必须承担一项任务，若给出某人不能从事的某些任务, 问要安排好工作,共有多少种方案?

http://codevs.cn/problem/1301/

分析

容斥原理的应用.

先看看样例:
四个人: A, B, C, D

A 不能选择: 2
B 不能选择: 2 3
C 不能选择: 3 4
D 不能选择: 4

总数是1~4全排列的个数 => 4! = 24
再考虑不能选的情况
那么
=>

采用 总数-非法个数 的方法计算, 而后者需用容斥原理计算.
answer :
= 4! - (|非法A + 非法B + 非法C + 非法D|)
= 4! - {|非法A| + |非法B| + |非法C| + |非法D| - |非法AB| - |非法AC| - |非法AD| - |非法BC| - |非法BD| - |非法CD| + |非法ABC| + |非法ABD| + |非法ACD| + |非法BCD| - |非法ABCD|}
= 4! - 3! - 2 * 3! - 2 * 3! - 3! + 2! + 2 * 2! + 2! + 3 * 2! + 2 * 2! + 2! - 1 - 1 - 1 - 1 + 0
= 4

容斥的实现

据说有三种实现容斥原理的方法 :
1. dfs
2. 队列数组
3. 二进制

只学了dfs法.
核心是统计各个阶乘的系数(coe), 记录在数组里, 最后高精统计.

根据 answer 的计算式子, 可以发现 : |P1 并 … Pm| m为奇数时, (n-m)! 的系数是负的. 容斥原理里这里是正的, 但别忘这里前头还有负号.

感觉这个dfs怪怪的… 先递归到底层, 又边回溯边更改.

变量表.
main() :
fac: 阶乘
cnt: 限制关系的个数
x[]: 人物
y[]: 任务
x[] <==> y[] // 一一对应

dfs() :
// 时间复杂度: O(2^15 = 32768)
coe[] 统计各个阶乘被计算了多少次
cur: 当前不匹配关系的编号
visx: 此人以考虑过
visy: 此任务已有人做
num: 当前正在统计 n-num 的阶乘的出现次数
|A1并A2并…并Anum|
num 为偶数 => coe[n-num]++
num 为奇数 => coe[n-num]–

代码

19ms 4MB

#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <sstream>
using namespace std;

const int maxn = 100 + 10;

struct bigint {
    int n, a[10000];
    static const int base = 10000;

    bigint operator += (const bigint& x) {
        n = max(n, x.n) + 1;
        for(int i = 0; i < n; i++) {
            a[i] += x.a[i];
            a[i + 1] += a[i] / base;
            a[i] %= base;
        }
        while(n > 0 && a[n - 1] == 0) n--;
        return *this;
    }

    bigint operator -= (const bigint& x) {
        for(int i = 0; i < n; i++) {
            if(a[i] < x.a[i]) {
                a[i] += base;
                a[i + 1] -= 1;
            }
            a[i] -= x.a[i];
        }
        while(n > 0 && a[n - 1] == 0) n--;
        return *this;
    }

    bigint operator * (const int& x) {
        bigint ans;
        ans.n = n + 1;
        memset(ans.a, 0, sizeof(ans.a));

        int rest = 0;
        for(int i = 0; i < ans.n; i++) {
            ans.a[i] = a[i] * x + rest;
            rest = ans.a[i] / base;
            ans.a[i] %= base;
        }
        while(ans.n > 0 && ans.a[ans.n - 1] == 0) ans.n--;
        return ans;
    }

    void print() {
        printf("%d", a[n - 1]);
        for(int i = n - 2; i >= 0; i--)
            printf("%04d", a[i]);
        printf("\n");
    }
};

int n, cnt, x[maxn], y[maxn], coe[maxn];
bool visx[maxn], visy[maxn];
bigint ans, fac[maxn];

// 当前正在考虑第 cur 对不匹配关系
// 正在计算 |A1 并 A2 并 ... 并 Anum|
void dfs(int cur, int num) {
    if(cur > cnt) coe[n - num] += (num & 1) ? -1 : 1;
    else {
        dfs(cur + 1, num);
        if(!visx[x[cur]] && !visy[y[cur]]) {
            visx[x[cur]] = visy[y[cur]] = 1;
            dfs(cur + 1, num + 1);
            visx[x[cur]] = visy[y[cur]] = 0;
        }
    }
}

int main() {
    cin >> n;
    fac[0] = (bigint) {1, {1}};
    for(int i = 1; i <= n; i++)
        fac[i] = fac[i - 1] * i;
    string tmp;
    getline(cin, tmp);
    for(int i = 0, j; i < n; i++) {
        string readline; // 不要定义在循环外, 因为如果没有读入readline, 会自动保留上次结果. 
        getline(cin, readline);
        stringstream ss(readline);
        while(ss >> j) {
            cnt++;
            x[cnt] = i;
            y[cnt] = j;
        }
    }
    dfs(1, 0);

    // 统计
    for(int i = 0; i <= n; i++) 
        if(coe[i] > 0) ans += fac[i] * coe[i];
    for(int i = 0; i <= n; i++) 
        if(coe[i] < 0) ans -= fac[i] * (-coe[i]);
    ans.print();

    return 0;
}

主页

http://blog.csdn.net/qq_21110267