[CODEVS 1301] 任务分配

描述

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

分析

容斥原理的应用.

先看看样例: 四个人: 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

;const int maxn = 100 + 10;struct bigint {int n, a[10000];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];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;}

主页

不论你在什么时候开始，重要的是开始之後就不要停止