[bzoj 1143]最长反链二分图最大匹配

Dilworth定理：偏序集能划分成的最少的全序集的个数与最大反链的元素个数相等。

证明：http://www.cnblogs.com/itlqs/p/6636222.html

题目让求的是最大反链的长度，因此可以转化为最少能划分成的链的个数。这个问题可以用二分图的最大匹配做。

建立一个二分图，两边都是n个点，原图的每个点 i 对应两个，在左边的叫做 i1, 在右边的叫做 i2 。

然后原图中如果存在一条边 (x, y)，那么就在二分图中建立 (x1, y2) 的边。

这样建立二分图之后，原图的点数 n - 二分图最大匹配 = 原图的最小路径覆盖（路径不能相交）。

这样为什么是对的呢？我们可以认为，开始时原图的每个点都是独立的一条路径，然后我们每次在二分图中选出一条边，就是将两条路径连接成一条路径，答案数就减少1。

因此最大的匹配就对应着减去的路径最多，也就是最少的链。

参考：http://www.cnblogs.com/JoeFan/p/4324380.html

要注意的是需要先做一次传递闭包，因为这里的边是具有传递性的，输入给出的所有u v边，还可以推出一些边，这些隐含边也要加进图里。（这样其实是把路径不能相交变成了路径可以相交）

#include<bits/stdc++.h>

using namespace std;

const int MAXN=;

int g[MAXN][MAXN];

int uN,vN;

int linker[MAXN];

bool used[MAXN];

bool dfs(int u)

{

    for(int v = ; v < vN; v++)

        if(g[u][v] && !used[v])

        {

            used[v] = true;

            if(linker[v] == - || dfs(linker[v]))

            {

                linker[v] = u;

                return true;

            }

        }

    return false;

}

int hungary()

{

    int res = ;

    memset(linker,-,sizeof(linker));

    for(int u = ; u < uN; u++)

    {

        memset(used,false,sizeof(used));

        if(dfs(u))res++;

    }

    return res;

}

int main()

{

    int n,m;

    while (~scanf("%d%d",&n,&m))

    {

        memset(g,,sizeof(g));

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

        {

            int u,v;

            scanf("%d%d",&u,&v);

            g[u-][v-]=;

        }

        for (int k=; k<n; k++)

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

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

                    if (g[i][k] && g[k][j]) g[i][j]=;

        uN=vN=n;

        printf("%d\n",n-hungary());

    }

    return ;

}

巴特西

[bzoj 1143]最长反链二分图最大匹配

最新文章

热门文章