描述

有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

總結

以上是生活随笔為你收集整理的[CODEVS 1301] 任务分配的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。