『Exclusive Access 2 dilworth定理 状压dp』

时间：2022-01-01 21:04:08

<更新提示>

<第一次更新>

<正文>

Exclusive Access 2

Description

给出 N 个点M 条边的无向图，定向得到有向无环图，使得最长路最短。

N ≤ 15, M ≤ 100

Input Format

第一行一个数M (1≤M≤100)。

接下来M行，每行两个大写字母（L 到 Z），最多出线15个不同的大写字母。每行的两个大写字母不会相同。

Output Format

第一行输出最长路最短的数值-1。

Sample Input

3

P Q

Q R

R P

Sample Output

1

解析

二分答案？想多了。

一个结论：有向无环图的最长链点数等于最小的点集划分数使得每个点集中不存在两点有路径。

证明：

由于最长链上的两点必然不能属于同一个点集，所以点集划分数大于等于最长链长度。

我们可以每次选出度为零的所有点划分在同一个点集中，若这些点之间有路径，则和他们出度为\(0\)矛盾，所以这样划分一定合法。同时，这样划分的集合数恰为原图的最长链长度。

我们其实变相证明了著名的\(dilworth\)定理：偏序集的最长链等于其最小反链划分。

然后直接枚举点集，状压预处理出其划分方式是否合法，然后枚举子集\(dp\)即可。

\(Code:\)

#include <bits/stdc++.h>

using namespace std;

const int N = 16;

int n,m,a[N][N],p[1<<N],f[1<<N];

vector < pair<char,char> > Link;

map <char,int> Hash;

int main(void)

{

    scanf("%d",&m);

    for (int i=1;i<=m;i++)

    {

        char c1,c2;

        cin >> c1 >> c2;

        Link.emplace_back(c1,c2);

        Hash[c1] = Hash[c2] = true;

    }

    map <char,int> :: iterator it;

    for (it=Hash.begin();it!=Hash.end();it++)

        it -> second = ++n;

    for ( auto e : Link )

        a[Hash[e.first]][Hash[e.second]] = a[Hash[e.second]][Hash[e.first]] = 1;

    memset( f , 0x3f , sizeof f );

    for (int S=1;S<1<<n;S++)

        for (int i=1;i<=n;i++)

            if ( S >> (i-1) & 1 )

                for (int j=i+1;j<=n;j++)

                    if ( S >> (j-1) & 1 )

                        p[S] |= a[i][j];

    f[0] = 0;

    for (int S=1;S<1<<n;S++)

        for (int T=S;T;T=S&(T-1))

            if ( p[T] == 0 )

                f[S] = min( f[S] , f[S^T] + 1 );

    printf("%d\n",f[(1<<n)-1]-2);

    return 0;

}

<后记>

相关文章