欢迎访问~原文出处——博客园-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 二分图匹配 最小链覆盖的更多相关文章
-
[图论训练]1143: [CTSC2008]祭祀river 二分图匹配
Description 在遥远的东方,有一个神秘的民族,自称Y族.他们世代居住在 水面上,奉龙王为神.每逢重大庆典, Y族都会在水面上举办盛大的祭祀活动.我们可以把Y族居住地水系看成一个由岔口和河道组 ...
-
BZOJ1143 [CTSC2008]祭祀river 【二分图匹配】
1143: [CTSC2008]祭祀river Time Limit: 10 Sec Memory Limit: 162 MB Submit: 3236 Solved: 1651 [Submit] ...
-
[BZOJ1143][CTSC2008]祭祀river(Dilworth定理+二分图匹配)
题意:给你一张n个点的DAG,最大化选择的点数,是点之间两两不可达. 要从Dilworth定理说起. Dilworth定理是定义在偏序集上的,也可以从图论的角度解释.偏序集中两个元素能比较大小,则在图 ...
-
【Floyd】【Dilworth定理】【最小路径覆盖】【匈牙利算法】bzoj1143 [CTSC2008]祭祀river
Dilworth定理,将最长反链转化为最小链覆盖.//貌似还能把最长上升子序列转化为不上升子序列的个数? floyd传递闭包,将可以重叠的最小链覆盖转化成不可重叠的最小路径覆盖.(引用:这样其实就是相 ...
-
bzoj1143: [CTSC2008]祭祀river 最长反链
题意:在遥远的东方,有一个神秘的民族,自称Y族.他们世代居住在水面上,奉龙王为神.每逢重大庆典, Y族都会在水面上举办盛大的祭祀活动.我们可以把Y族居住地水系看成一个由岔口和河道组成的网络.每条河道连 ...
-
bzoj1143: [CTSC2008]祭祀river &;&; bzoj27182718: [Violet 4]毕业旅行
其实我至今不懂为啥强联通缩点判入度会错... 然后这个求的和之前那道组合数学一样,就是最长反链=最小链覆盖=最大独立集. #include<cstdio> #include<iost ...
-
2018.08.20 bzoj1143: [CTSC2008]祭祀river(最长反链)
传送门 一道简单的求最长反链. 反链简单来说就是一个点集,里面任选两个点u,v都保证从u出发到不了v且v出发到不了u. 链简单来说就是一个点集,里面任选两个点u,v都保证从u出发可以到达v或者v出发可 ...
-
[BZOJ1143][CTSC2008]祭祀river(最长反链)
题目:http://www.lydsy.com:808/JudgeOnline/problem.php?id=1143 分析: 最长反链==最小路径覆盖==n-二分图最大匹配数 某神犇对二分图的总结: ...
-
BZOJ1143: [CTSC2008]祭祀river 网络流_Floyd_最大独立集
Description 在遥远的东方,有一个神秘的民族,自称Y族.他们世代居住在水面上,奉龙王为神.每逢重大庆典, Y族都 会在水面上举办盛大的祭祀活动.我们可以把Y族居住地水系看成一个由岔口和河道组 ...
随机推荐
-
将n阶方阵左下半三角中的元素值置0.
/*===================================== 将n阶方阵左下半三角中的元素值置0. 0<n<10. =========================== ...
-
10 款提高开发效率的 jQuery/CSS3 组件
前端开发是一项十分繁琐而又耗体力的工作,如何更有效率的开发我们的应用,很多人会选择适当地使用一些jQuery插件.今天就要给大家分享10款可以提高开发效率的jQuery/CSS3组件.部分插件可以下载 ...
-
【搜索引擎Jediael开发笔记1】搜索引擎初步介绍及网络爬虫
详细可参考 (1)书箱:<这就是搜索引擎><自己动手写网络爬虫><解密搜索引擎打桩实践> (2)[搜索引擎基础知识1]搜索引擎的技术架构 (3)[搜索引擎基础知识2 ...
-
STURTS2 HELLOWORLD
4. <?xml version="1.0" encoding="UTF-8"?> <!DOCTYPE struts PUBLIC " ...
-
Luogu P5292 [HNOI2019]校园旅行
非常妙的一道思博题啊,不愧是myy出的题 首先我们考虑一个暴力DP,直接开一个数组\(f_{i,j}\)表示\(i\to j\)的路径能否构成回文串 考虑直接拿一个队列来转移,队列里存的都是\(f_{ ...
-
kotlin 第一个Android项目
一.创建过程 二.TextView点击事件 class MainActivity : AppCompatActivity() { lateinit var tv:TextView; //初始化Text ...
-
Activity声明周期1
oncreate():在Activity对象第一次创建时调用 onStart():当Activity变得可见时调用该函数 onResume():当Activity开始准备于用户交互时调用该方法(即获得 ...
-
MySql之视图的使用
一:视图是什么 视图相当于一个窗口,一个基于具体数据库表.定义了相关查询规则 的窗口. 建立视图,可以重用一些复杂的查询语句. 建立视图,相当于定义了一系列查询操作:从视图查询数据,相当于在调用 ...
-
python面向对象魔术方法补充
一.描述符 在 面向对象 编程中 定义一个(没有定义方法)类:class person , 在这个类里面,有name,age, heigth, weight,等等属性, 这个类就可以看作一个对 per ...
-
IOS使用SourceTree
一.安装sourceTree 1.下载 访问SourceTree 软件官方下载地址 : https://www.sourcetreeapp.com 下载macos版本 2.安装 安装和windows安 ...