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 祭祀的更多相关文章
-
[BZOJ 1143] 祭祀river
Link:https://www.lydsy.com/JudgeOnline/problem.php?id=1143 Solution: 一道最长反链的模板题 由Dilworth定理可知:最小链覆盖数 ...
-
[BZOJ 1143] [CTSC2008] 祭祀river 【最长反链】
题目链接:BZOJ - 1143 题目分析 这道题在BZOJ上只要求输出可选的最多的祭祀地点个数,是一道求最长反链长度的裸题. 下面给出一些相关知识: 在有向无环图中,有如下的一些定义和性质: 链:一 ...
-
BZOJ 1143 1143: [CTSC2008]祭祀river 最长反链
1143: [CTSC2008]祭祀river Description 在遥远的东方,有一个神秘的民族,自称Y族.他们世代居住在水面上,奉龙王为神.每逢重大庆典, Y族都会在水面上举办盛大的祭祀活动. ...
-
BZOJ 1143: [CTSC2008]祭祀river 最长反链
1143: [CTSC2008]祭祀river Time Limit: 1 Sec Memory Limit: 256 MB 题目连接 http://www.lydsy.com/JudgeOnline ...
-
Bzoj 2718: [Violet 4]毕业旅行 &;&; Bzoj 1143: [CTSC2008]祭祀river 传递闭包,二分图匹配,匈牙利,bitset
1143: [CTSC2008]祭祀river Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 1878 Solved: 937[Submit][St ...
-
bzoj 1143: [CTSC2008]祭祀river / 2718: [Violet 4]毕业旅行 -- 二分图匹配
1143: [CTSC2008]祭祀river Time Limit: 10 Sec Memory Limit: 162 MB Description 在遥远的东方,有一个神秘的民族,自称Y族.他们 ...
-
BZOJ 1143: [CTSC2008]祭祀river 最大独立集
题目链接: http://www.lydsy.com/JudgeOnline/problem.php?id=1143 题解: 给你一个DAG,求最大的顶点集,使得任意两个顶点之间不可达. 把每个顶点v ...
-
BZOJ 1143 [CTSC2008]祭祀river(二分图匹配)
[题目链接] http://www.lydsy.com/JudgeOnline/problem.php?id=1143 [题目大意] 给出一张有向图,问最大不连通点集,连通具有传递性 [题解] 我们将 ...
-
BZOJ 1143: [CTSC2008]祭祀river(最大独立集)
题面: https://www.lydsy.com/JudgeOnline/problem.php?id=1143 一句话题意:给一个DAG(有向无环图),求选出尽量多的点使这些点两两不可达,输出点个 ...
随机推荐
-
测试MailUtils,作用是发邮件
package cn.itcast.test; import java.io.IOException; import javax.mail.MessagingException; import jav ...
-
js中查找相同的几种函数
function findInArr(arr,num){ for(var i=0;i<arr.length;i++){ if(arr[i]==num){ return true; } } ret ...
-
android贪吃蛇(超级简陋版)
public class body { public int ax;//代表X周变量 public int ay;//代表Y轴变量 public int getAx() { return ax; } ...
-
JGibbLDA:java版本的LDA(Latent Dirichlet Allocation)实现、修改及使用
转载自:http://blog.csdn.net/memray/article/details/16810763 一.概述 JGibbLDA是一个java版本的LDA(Latent Dirichl ...
-
java之内存管理
对于JVM的垃圾回收机制来说,是否回收一个对象的标准在于:是否还有引用变量引用该对象,只要有引用变量引用该对象,垃圾回收机制就不会回收它. 强引用:创建一个对象,并把这个对象赋给一个引用变量.这种引用 ...
-
CapsLock indicator on Ubuntu for Thinkpad
http://askubuntu.com/questions/292535/how-to-get-caps-num-scroll-lock-keys-osd-notification sudo add ...
-
Android进阶(十一)Android系统架构讲解
如果说一个成功男人的背后会有一个默默支持的女人的话,那么一个优越稳定的平台背后必有一个成熟的系统架构所支撑着.那么,Android的系统架构是怎么样的呢?从下图我们可以从整体上有个大致的了解(图片来源 ...
-
MTK 快速开机 技术详解
Android version 2.3.5 首先查看Settings里控制开关 01 // 获取当前状态 02 boolean ipoSettingEnabled = Settings.System. ...
-
Java集合框架相关知识整理
1.常见的集合有哪些? Collection接口和Map接口是所有集合框架的父接口 Collection接口的子接口包括:Set接口和List接口 Map接口的实现类主要有:HashMap ...
-
Confluence 6 PostgreSQL 输入你的数据库细节
在 Confluence 的设置安装向导中,将会指导你 Confluence 如何连接到你的数据库.请确定选择 "My own database". 使用 JDBC 连接(默认) ...