BZOJ1143 [CTSC2008]祭祀river 二分图匹配 最小链覆盖

时间:2022-04-17 09:59:04

欢迎访问~原文出处——博客园-zhouzhendong

去博客园看该题解


题目传送门 - BZOJ1143


题意概括

  给出一个有向图。求最小链覆盖。


题解

  首先说两个概念:

    链:一条链是一些点的集合,链上任意两个点x, y,满足要么 x 能到达 y ,要么 y 能到达 x 。

    反链:一条反链是一些点的集合,链上任意两个点x, y,满足 x 不能到达 y,且 y 也不能到达 x。

  这题就是求最长反链长度。

  有两个定理:

  最长反链长度 = 最小链覆盖

  最长链长度 = 最小反链覆盖

  这题明显可以使用第一个。

  那么只需要floyd跑一跑,然后二分图匹配就可以了。

  代码比较短。


代码

#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
using namespace std;
const int N=100+5,N2=N*2;
int n,m,match[N2];
bool g[N][N],g2[N2][N2],vis[N2];
bool dfs(int x){
for (int i=1;i<=n;i++){
int y=i+n;
if (!vis[y]&&g2[x][y]){
vis[y]=1;
if (match[y]==-1||dfs(match[y])){
match[y]=x;
return 1;
}
}
}
return 0;
}
int main(){
memset(g,0,sizeof g);
memset(g2,0,sizeof g2);
scanf("%d%d",&n,&m);
for (int i=1,a,b;i<=m;i++){
scanf("%d%d",&a,&b);
g[a][b]=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][j]||(g[i][k]&&g[k][j]);
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
if (g[i][j])
g2[i][j+n]=1;
int cnt=0;
memset(match,-1,sizeof match);
for (int i=1;i<=n;i++){
memset(vis,0,sizeof vis);
if (dfs(i))
cnt++;
}
printf("%d\n",n-cnt);
return 0;
}

  

BZOJ1143 [CTSC2008]祭祀river 二分图匹配 最小链覆盖的更多相关文章

  1. &lbrack;图论训练&rsqb;1143&colon; &lbrack;CTSC2008&rsqb;祭祀river 二分图匹配

    Description 在遥远的东方,有一个神秘的民族,自称Y族.他们世代居住在 水面上,奉龙王为神.每逢重大庆典, Y族都会在水面上举办盛大的祭祀活动.我们可以把Y族居住地水系看成一个由岔口和河道组 ...

  2. BZOJ1143 &lbrack;CTSC2008&rsqb;祭祀river 【二分图匹配】

    1143: [CTSC2008]祭祀river Time Limit: 10 Sec  Memory Limit: 162 MB Submit: 3236  Solved: 1651 [Submit] ...

  3. &lbrack;BZOJ1143&rsqb;&lbrack;CTSC2008&rsqb;祭祀river&lpar;Dilworth定理&plus;二分图匹配&rpar;

    题意:给你一张n个点的DAG,最大化选择的点数,是点之间两两不可达. 要从Dilworth定理说起. Dilworth定理是定义在偏序集上的,也可以从图论的角度解释.偏序集中两个元素能比较大小,则在图 ...

  4. 【Floyd】【Dilworth定理】【最小路径覆盖】【匈牙利算法】bzoj1143 &lbrack;CTSC2008&rsqb;祭祀river

    Dilworth定理,将最长反链转化为最小链覆盖.//貌似还能把最长上升子序列转化为不上升子序列的个数? floyd传递闭包,将可以重叠的最小链覆盖转化成不可重叠的最小路径覆盖.(引用:这样其实就是相 ...

  5. bzoj1143&colon; &lbrack;CTSC2008&rsqb;祭祀river 最长反链

    题意:在遥远的东方,有一个神秘的民族,自称Y族.他们世代居住在水面上,奉龙王为神.每逢重大庆典, Y族都会在水面上举办盛大的祭祀活动.我们可以把Y族居住地水系看成一个由岔口和河道组成的网络.每条河道连 ...

  6. bzoj1143&colon; &lbrack;CTSC2008&rsqb;祭祀river &amp&semi;&amp&semi; bzoj27182718&colon; &lbrack;Violet 4&rsqb;毕业旅行

    其实我至今不懂为啥强联通缩点判入度会错... 然后这个求的和之前那道组合数学一样,就是最长反链=最小链覆盖=最大独立集. #include<cstdio> #include<iost ...

  7. 2018&period;08&period;20 bzoj1143&colon; &lbrack;CTSC2008&rsqb;祭祀river(最长反链)

    传送门 一道简单的求最长反链. 反链简单来说就是一个点集,里面任选两个点u,v都保证从u出发到不了v且v出发到不了u. 链简单来说就是一个点集,里面任选两个点u,v都保证从u出发可以到达v或者v出发可 ...

  8. &lbrack;BZOJ1143&rsqb;&lbrack;CTSC2008&rsqb;祭祀river&lpar;最长反链)

    题目:http://www.lydsy.com:808/JudgeOnline/problem.php?id=1143 分析: 最长反链==最小路径覆盖==n-二分图最大匹配数 某神犇对二分图的总结: ...

  9. BZOJ1143&colon; &lbrack;CTSC2008&rsqb;祭祀river 网络流&lowbar;Floyd&lowbar;最大独立集

    Description 在遥远的东方,有一个神秘的民族,自称Y族.他们世代居住在水面上,奉龙王为神.每逢重大庆典, Y族都 会在水面上举办盛大的祭祀活动.我们可以把Y族居住地水系看成一个由岔口和河道组 ...

随机推荐

  1. 将n阶方阵左下半三角中的元素值置0&period;

    /*===================================== 将n阶方阵左下半三角中的元素值置0. 0<n<10. =========================== ...

  2. 10 款提高开发效率的 jQuery&sol;CSS3 组件

    前端开发是一项十分繁琐而又耗体力的工作,如何更有效率的开发我们的应用,很多人会选择适当地使用一些jQuery插件.今天就要给大家分享10款可以提高开发效率的jQuery/CSS3组件.部分插件可以下载 ...

  3. 【搜索引擎Jediael开发笔记1】搜索引擎初步介绍及网络爬虫

    详细可参考 (1)书箱:<这就是搜索引擎><自己动手写网络爬虫><解密搜索引擎打桩实践> (2)[搜索引擎基础知识1]搜索引擎的技术架构 (3)[搜索引擎基础知识2 ...

  4. STURTS2 HELLOWORLD

    4. <?xml version="1.0" encoding="UTF-8"?> <!DOCTYPE struts PUBLIC &quot ...

  5. Luogu P5292 &lbrack;HNOI2019&rsqb;校园旅行

    非常妙的一道思博题啊,不愧是myy出的题 首先我们考虑一个暴力DP,直接开一个数组\(f_{i,j}\)表示\(i\to j\)的路径能否构成回文串 考虑直接拿一个队列来转移,队列里存的都是\(f_{ ...

  6. kotlin 第一个Android项目

    一.创建过程 二.TextView点击事件 class MainActivity : AppCompatActivity() { lateinit var tv:TextView; //初始化Text ...

  7. Activity声明周期1

    oncreate():在Activity对象第一次创建时调用 onStart():当Activity变得可见时调用该函数 onResume():当Activity开始准备于用户交互时调用该方法(即获得 ...

  8. MySql之视图的使用

    一:视图是什么 视图相当于一个窗口,一个基于具体数据库表.定义了相关查询规则 的窗口. 建立视图,可以重用一些复杂的查询语句.    建立视图,相当于定义了一系列查询操作:从视图查询数据,相当于在调用 ...

  9. python面向对象魔术方法补充

    一.描述符 在 面向对象 编程中 定义一个(没有定义方法)类:class person , 在这个类里面,有name,age, heigth, weight,等等属性, 这个类就可以看作一个对 per ...

  10. IOS使用SourceTree

    一.安装sourceTree 1.下载 访问SourceTree 软件官方下载地址 : https://www.sourcetreeapp.com 下载macos版本 2.安装 安装和windows安 ...