BZOJ1143:祭祀river(二分图求有向图的最大点独立集)
2024-08-30 16:00:20
在遥远的东方,有一个神秘的民族,自称Y族。他们世代居住在水面上,奉龙王为神。每逢重大庆典, Y族都
会在水面上举办盛大的祭祀活动。我们可以把Y族居住地水系看成一个由岔口和河道组成的网络。每条河道连接着
两个岔口,并且水在河道内按照一个固定的方向流动。显然,水系中不会有环流(下图描述一个环流的例子)。
由于人数众多的原因,Y族的祭祀活动会在多个岔口上同时举行。出于对龙王的尊重,这些祭祀地点的选择必
须非常慎重。准确地说,Y族人认为,如果水流可以从一个祭祀点流到另外一个祭祀点,那么祭祀就会失去它神圣
的意义。族长希望在保持祭祀神圣性的基础上,选择尽可能多的祭祀的地点。
Input
第一行包含两个用空格隔开的整数N、M,分别表示岔口和河道的数目,岔口从1到N编号。
接下来M行,每行包含两个用空格隔开的整数u、v,
描述一条连接岔口u和岔口v的河道,水流方向为自u向v。
N≤100 ,M≤1000
Output
第一行包含一个整数K,表示最多能选取的祭祀点的个数。
Sample Input
4 4
1 2
3 4
3 2
4 2
Sample Output
2
题意:给定有向图,问最多可以选择多少个点,使他们之间互不相连(其实就是最大独立集)。
思路:有向图转化为二分图,有:最小点覆盖=最大匹配。 最大独立集=总-最小点覆盖。
注意:如果是最小路径覆盖的题,不需要闭包传递。 但是最大独立集需要闭包传递。
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=;
int mp[maxn][maxn],used[maxn],linker[maxn],N;
bool find(int u,int F)
{
for(int i=;i<=N;i++){
if(mp[u][i]&&used[i]!=F){
used[i]=F;
if(!linker[i]||find(linker[i],F)){
linker[i]=u;
return true;
}
}
}
return false;
}
void folyd()
{
for(int k=;k<=N;k++)
for(int i=;i<=N;i++)
if(mp[i][k])
for(int j=;j<=N;j++)
if(mp[k][j]) mp[i][j]=;
}
int main()
{
int M,u,v,ans=;
scanf("%d%d",&N,&M);
for(int i=;i<=M;i++){
scanf("%d%d",&u,&v);
mp[u][v]=;
}
folyd();
for(int i=;i<=N;i++)
if(find(i,i)) ans++;
printf("%d\n",N-ans);
return ;
}
最新文章
- 【MySQL】 查询某个数据库有多少张数据表
- 无废话WCF
- eclipse安装color theme插件
- Hibernate简单实例
- oracle中文显示为问号
- MFC RadioButton
- php---PHP setcookie()
- MongoDB 中遇到的一些错误
- [译]GotW #2: Temporary Objects
- javascript单例模式及开发实践
- 1.JAVA-Hello World
- mysql7.5.x删除重新安装
- PHP实现类似题库抽题效果
- 【Spark工作原理】stage划分原理理解
- 【转载】Vue项目自动转换 px 为 rem,高保真还原设计图
- Elasticsearch 基础概念知识
- django中的字段类型
- C# winform 安装服务
- ButterKnifeZelezny简单使用教程
- webpack 入门总结和实践(按需异步加载,css单独打包,生成多个入口文件)
热门文章
- 【linux】ls与ll区别
- [Poj2096]Collecting Bugs(入门期望dp)
- MySQL事务及Spring事务管理
- ArcEngine中IFeatureClass.Search(filter, Recycling)方法中Recycling参数的理解
- Oracle 行转列小结
- 【转】c++ 如何批量初始化数组 fill和fill_n函数的应用
- Linux内核project导论——网络:Filter(LSF、BPF、eBPF)
- 深入浅出Redis(三)高级特性:管道
- Vs2012在Linux开发中的应用(5):项目属性的定义
- ascii与unicode,utf-8小结