BZOJ 1143 祭祀

时间:2022-09-28 14:49:10

Description

在遥远的东方,有一个神秘的民族,自称Y族。他们世代居住在水面上,奉龙王为神。每逢重大庆典, Y族都会在水面上举办盛大的祭祀活动。我们可以把Y族居住地水系看成一个由岔口和河道组成的网络。每条河道连接着两个岔口,并且水在河道内按照一个固定的方向流动。显然,水系中不会有环流(下图描述一个环流的例子)。

由于人数众多的原因,Y族的祭祀活动会在多个岔口上同时举行。出于对龙王的尊重,这些祭祀地点的选择必须非常慎重。准确地说,Y族人认为,如果水流可以从一个祭祀点流到另外一个祭祀点,那么祭祀就会失去它神圣的意义。族长希望在保持祭祀神圣性的基础上,选择尽可能多的祭祀的地点。

Input

第一行包含两个用空格隔开的整数\(N,M\),分别表示岔口和河道的数目,岔口从\(1\)到\(N\)编号。接下来\(M\)行,每行包含两个用空格隔开的整数\(u,v\),描述一条连接岔口\(u\)和岔口\(v\)的河道,水流方向为自\(u\)向\(v\)。

Output

第一行包含一个整数\(K\),表示最多能选取的祭祀点的个数。

Sample Input

4 4

1 2

3 4

3 2

4 2

Sample Output

2

HINT

\(N \le 100,M \le 1000\)

一个二分图最大独立集裸题(独立集:图中任意两个顶点都不相连的顶点集合)。

若\(A\)能到\(B\),那么在二分图中\(A_{1}\)与\(B_{2}\)连接一条边(连边我们可以用floyed)。最后的答案即为总点数-最大匹配数。

二分图的一些证明定理请戳这里

#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std; #define maxn (110)
#define maxm (1010)
int n,m,cho[maxn]; bool f[maxn][maxn],used[maxn]; inline int find(int x)
{
for (int i = 1;i <= n;++i)
if (f[x][i]&&!used[i])
{
used[i] = true;
if (!cho[i]||find(cho[i])) { cho[i] = x; return true; }
}
return false;
} inline int hungry()
{
int ret = 0;
for (int i = 1;i <= n;++i)
{
memset(used,false,sizeof(used));
if (find(i)) ret++;
}
return ret;
} int main()
{
freopen("1143.in","r",stdin);
freopen("1143.out","w",stdout);
scanf("%d %d",&n,&m);
while (m--) { int a,b; scanf("%d %d",&a,&b); f[a][b] = true; }
for (int k = 1;k <= n;++k)
for (int i = 1;i <= n;++i) if (f[i][k])
for (int j = 1;j <= n;++j)
f[i][j] |= (f[i][k]&f[k][j]);
printf("%d",n-hungry());
fclose(stdin); fclose(stdout);
return 0;
}

BZOJ 1143 祭祀的更多相关文章

  1. &lbrack;BZOJ 1143&rsqb; 祭祀river

    Link:https://www.lydsy.com/JudgeOnline/problem.php?id=1143 Solution: 一道最长反链的模板题 由Dilworth定理可知:最小链覆盖数 ...

  2. &lbrack;BZOJ 1143&rsqb; &lbrack;CTSC2008&rsqb; 祭祀river 【最长反链】

    题目链接:BZOJ - 1143 题目分析 这道题在BZOJ上只要求输出可选的最多的祭祀地点个数,是一道求最长反链长度的裸题. 下面给出一些相关知识: 在有向无环图中,有如下的一些定义和性质: 链:一 ...

  3. BZOJ 1143 1143&colon; &lbrack;CTSC2008&rsqb;祭祀river 最长反链

    1143: [CTSC2008]祭祀river Description 在遥远的东方,有一个神秘的民族,自称Y族.他们世代居住在水面上,奉龙王为神.每逢重大庆典, Y族都会在水面上举办盛大的祭祀活动. ...

  4. BZOJ 1143&colon; &lbrack;CTSC2008&rsqb;祭祀river 最长反链

    1143: [CTSC2008]祭祀river Time Limit: 1 Sec Memory Limit: 256 MB 题目连接 http://www.lydsy.com/JudgeOnline ...

  5. Bzoj 2718&colon; &lbrack;Violet 4&rsqb;毕业旅行 &amp&semi;&amp&semi; Bzoj 1143&colon; &lbrack;CTSC2008&rsqb;祭祀river 传递闭包&comma;二分图匹配&comma;匈牙利&comma;bitset

    1143: [CTSC2008]祭祀river Time Limit: 10 Sec  Memory Limit: 162 MBSubmit: 1878  Solved: 937[Submit][St ...

  6. bzoj 1143&colon; &lbrack;CTSC2008&rsqb;祭祀river &sol; 2718&colon; &lbrack;Violet 4&rsqb;毕业旅行 -- 二分图匹配

    1143: [CTSC2008]祭祀river Time Limit: 10 Sec  Memory Limit: 162 MB Description 在遥远的东方,有一个神秘的民族,自称Y族.他们 ...

  7. BZOJ 1143&colon; &lbrack;CTSC2008&rsqb;祭祀river 最大独立集

    题目链接: http://www.lydsy.com/JudgeOnline/problem.php?id=1143 题解: 给你一个DAG,求最大的顶点集,使得任意两个顶点之间不可达. 把每个顶点v ...

  8. BZOJ 1143 &lbrack;CTSC2008&rsqb;祭祀river(二分图匹配)

    [题目链接] http://www.lydsy.com/JudgeOnline/problem.php?id=1143 [题目大意] 给出一张有向图,问最大不连通点集,连通具有传递性 [题解] 我们将 ...

  9. BZOJ 1143&colon; &lbrack;CTSC2008&rsqb;祭祀river(最大独立集)

    题面: https://www.lydsy.com/JudgeOnline/problem.php?id=1143 一句话题意:给一个DAG(有向无环图),求选出尽量多的点使这些点两两不可达,输出点个 ...

随机推荐

  1. 测试MailUtils&comma;作用是发邮件

    package cn.itcast.test; import java.io.IOException; import javax.mail.MessagingException; import jav ...

  2. js中查找相同的几种函数

    function findInArr(arr,num){ for(var i=0;i<arr.length;i++){ if(arr[i]==num){ return true; } } ret ...

  3. android贪吃蛇(超级简陋版)

    public class body { public int ax;//代表X周变量 public int ay;//代表Y轴变量 public int getAx() { return ax; } ...

  4. JGibbLDA:java版本的LDA&lpar;Latent Dirichlet Allocation&rpar;实现、修改及使用

    转载自:http://blog.csdn.net/memray/article/details/16810763   一.概述 JGibbLDA是一个java版本的LDA(Latent Dirichl ...

  5. java之内存管理

    对于JVM的垃圾回收机制来说,是否回收一个对象的标准在于:是否还有引用变量引用该对象,只要有引用变量引用该对象,垃圾回收机制就不会回收它. 强引用:创建一个对象,并把这个对象赋给一个引用变量.这种引用 ...

  6. CapsLock indicator on Ubuntu for Thinkpad

    http://askubuntu.com/questions/292535/how-to-get-caps-num-scroll-lock-keys-osd-notification sudo add ...

  7. Android进阶&lpar;十一&rpar;Android系统架构讲解

    如果说一个成功男人的背后会有一个默默支持的女人的话,那么一个优越稳定的平台背后必有一个成熟的系统架构所支撑着.那么,Android的系统架构是怎么样的呢?从下图我们可以从整体上有个大致的了解(图片来源 ...

  8. MTK 快速开机 技术详解

    Android version 2.3.5 首先查看Settings里控制开关 01 // 获取当前状态 02 boolean ipoSettingEnabled = Settings.System. ...

  9. Java集合框架相关知识整理

    1.常见的集合有哪些? Collection接口和Map接口是所有集合框架的父接口    Collection接口的子接口包括:Set接口和List接口    Map接口的实现类主要有:HashMap ...

  10. Confluence 6 PostgreSQL 输入你的数据库细节

    在 Confluence 的设置安装向导中,将会指导你 Confluence 如何连接到你的数据库.请确定选择 "My own database". 使用 JDBC 连接(默认) ...