1301 任务分配

2003年浙江省队选拔赛

时间限制: 1 s

空间限制: 128000 KB

题目等级 : 大师 Master

题目描述 Description

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

输入描述 Input Description

输入文件第1行为N(1<=N<=100), 以下N行，其中第i+1行表示第i个人不能从事的任务编号, 任务之间用空隔分开, 若第i个人没有限制条件，则第i+1行为空行, 所有人员不能从事的任务之和不大于25。

输出描述 Output Description

输出文件只有1行，为所有满足条件的分配方案数。

样例输入 Sample Input

2 3

3 4

样例输出 Sample Output

数据范围及提示 Data Size & Hint

如题

分类标签 Tags 点此展开

开放性试题搜索省队选拔赛 2003年

分析

容斥原理的应用.

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

来自：http://blog.csdn.net/qq_21110267/article/details/43882591

AC代码：

#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <sstream>
using namespace std;
const int maxn=100+10;
struct bigint{
    static const int base=10000;
    int n,a[base];
    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("
");
    }
};
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;
        return ;
    } 
    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;
}