ACM-ICPC 2017 Asia Nanning M. The Maximum Unreachable Node Set

题目链接https://nanti.jisuanke.com/t/19979

题意:给定一张DAG,求最大的点集使得两两点之间不可达。

思路:最长反链的定义:链是一个点的集合,这个集合中任意两个元素vu,要么v能走到u,要么u能走到v。反链是一个点的集合,这个集合中任意两点谁也不能走到谁。最长反链是反链中最长的那个。Dilworth定理:最小链覆盖数=最长反链长度。这题就是要求最长反链的长度,所以我们转成求最小链覆盖,然后最小链覆盖就是最小路径可重复点覆盖问题,我们跑一下传递闭包,拆点二分图求最大匹配就好了,是一个很经典的题目。现在想想南宁的时候自己是真的什么都不会唉...太垃圾了我...各种裸题不会做..还要加油啊...

#include <bits/stdc++.h>
using namespace std;
template<typename T>
inline T read(T&x){
    x=0;int f=0;char ch=getchar();
    while (ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar();
    while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x=f?-x:x;
}
const int N=100+10;
int T,res,n,m,u,v,i,j,k,match[N];
bool vis[N][N],vis2[N];
bool dfs(int x){
    for (int i=1;i<=n;i++){
        if (vis[x][i]&&!vis2[i]){
            vis2[i]=1;
            if (!match[i]||dfs(match[i])){
                match[i]=x;
                return 1;
            }
        }
    }
    return 0;
}
int main(){
    for (read(T);T--;){
        read(n),read(m);
        memset(vis,0,sizeof(vis));
        memset(match,0,sizeof(match));
        for (i=1;i<=m;i++){
            read(u),read(v);
            vis[u][v]=1;
        }
        for (i=1;i<=n;i++) vis[i][i]=1;
        for (k=1;k<=n;k++){
            for (i=1;i<=n;i++){
                for (j=1;j<=n;j++){
                    vis[i][j]|=vis[i][k]&&vis[k][j];
                }
            }
        }
        for (i=1;i<=n;i++) vis[i][i]=0;
        for (res=n,i=1;i<=n;i++){
            memset(vis2,0,sizeof(vis2));
            res-=dfs(i);
        }
        printf("%d\n",res);
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注