首页 > 其他 > 详细

[BZOJ1143][CTSC2008]祭祀river

时间:2018-01-22 18:16:36      阅读:246      评论:0      收藏:0      [点我收藏+]

题面戳我

sol

介绍几个基于有向无环图(DAG)的概念:

广义上来说,链是一个点集,其中任意两点u,v,都满足[u能到达v]+[v能到达u]=1(就是说两个只满足其一)

反链

与链的定义类似,就是任意两个点都无法到达。
这个题要求的是最长反链
而最长反链等于最小链覆盖 (我不会证)

最小链覆盖

用最少的链去覆盖整张图,使得每个点被覆盖至少一次(不同于最小路径覆盖只能覆盖每个点一次)
而要求最小链覆盖,只要先跑一次传递闭包(只是说得高大上一点啦,其实就是个\(Floyed\)),然后就变成了最小路径覆盖。最小路径覆盖可以直接跑二分图最大匹配(每个点匹配一个后继)

code

压行压得丧心病狂

#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 105;
int gi()
{
    int x=0,w=1;char ch=getchar();
    while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
    if (ch=='-') w=0,ch=getchar();
    while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
    return w?x:-x;
}
int n,m,g[N][N],matching[N],check[N],id;
bool dfs(int u)
{
    for (int i=1;i<=n;i++)
    {
        if (!g[u][i]||check[i]==id) continue;
        check[i]=id;
        if (!matching[i]||dfs(matching[i]))
            return matching[i]=u,true;
    }
    return false;
}
int Hungarian()
{
    int ans=0;
    for (int i=1;i<=n;i++) {id++;if (dfs(i)) ans++;}
    return ans;
}
int main()
{
    n=gi();m=gi();
    for (int i=1;i<=m;i++)
        g[gi()][gi()]=1;
    for (int k=1;k<=n;k++)
        for (int i=1;i<=n;i++)
            for (int j=1;j<=n;j++)
                g[i][j]|=g[i][k]&g[k][j];
    return printf("%d\n",n-Hungarian()),0;
}

[BZOJ1143][CTSC2008]祭祀river

原文:https://www.cnblogs.com/zhoushuyu/p/8330131.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!