2018年长沙理工大学第十三届程序设计竞赛 K. zzq的离散数学教室2(dilworth定理+有向图可相交路径覆盖 dinic版)

本文主要是介绍2018年长沙理工大学第十三届程序设计竞赛 K. zzq的离散数学教室2(dilworth定理+有向图可相交路径覆盖 dinic版),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目

在这个题目中,集合中有n个元素,编号从1到n。它们之间共有m对偏序关系,每一对偏序关系的表示形式为以空格分开的两个编号:x y。含义是x和y之间有关系≤。(这里的≤不是传统意义上的小于等于,可以理解为从y到x的一条有向边),记做:x≤y。同时这些关系也具有传递性,例如,如果x≤y并且y≤z,那么可以得到x≤z。数据保证不会出现同时有x≤y,y≤z,z≤x的情况。

现在我们的问题是,要你从n个元素里尽可能多的选出一些元素,使得这些元素之间不满足偏序关系。(即这些点中,任意两点都不存在偏序关系).问你最多能选几个元素。 

T组样例,n<=1e5,sumn<=3e5,m<=2n

思路来源

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=45181859

题解

dilworth定理,最长反链=最小链覆盖,

在有向图中,反链即为没有上下游关系的两个点

偏序最大独立集=有向图最小链覆盖,可相交

dinic建图即可,传统建图方法先求传递闭包然后最大匹配,

但是n=1e5这样边开不下

于是,考虑这样一种dinic建图方法,

1. 将i拆成i和i+n两个点,

2. 将原来的有向边x->y,看做是x->y+n

3. 超级源点s->i

4. (i+n)->超级汇点e

5. 对于不直接相邻,也就是上下游关系即可连边的条件,额外建边(i+n)->i

左侧s->i可以看成是选了一个起点,x->y+n如果不相交的话就是选了一个终点,

y+n->y相当于允许退回去,不把y当终点,后面还可以选其他点当终点

最终y+n->e认为是选了一个终点

这个退回去重选的边的权值,只要大于最大流即可,这里置INF,

x->y+n的边的权值,因为也要过重选的流量,所以也置INF

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<map> 
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
const int maxn=2e5+10;
const int maxm=2e6+10;
int level[maxn];
int head[maxn],cnt;
int t,n,m;
int ss,ee;
struct edge{int v,nex;ll w;}e[maxm];
void init(int n)
{cnt=0;for(int i=1;i<=n;++i){head[i]=-1;}
}
void add(int u,int v,ll w)
{e[cnt].v=v;e[cnt].w=w;e[cnt].nex=head[u];head[u]=cnt++;
}
void add2(int u,int v,ll w,bool op)//是否为有向图 
{add(u,v,w);add(v,u,op?0:w);
}
bool bfs(int s,int t)
{queue<int>q;memset(level,0,sizeof level);level[s]=1;q.push(s);while(!q.empty()){int x=q.front();q.pop();if(x==t)return 1;for(int u=head[x];~u;u=e[u].nex){int v=e[u].v;ll w=e[u].w;if(!level[v]&&w){level[v]=level[x]+1;q.push(v);}}}return 0;
}
ll dfs(int u,ll maxf,int t)
{if(u==t)return maxf;ll ret=0;for(int i=head[u];~i;i=e[i].nex){int v=e[i].v;ll w=e[i].w;if(level[u]+1==level[v]&&w){ll MIN=min(maxf-ret,w);w=dfs(v,MIN,t);e[i].w-=w;e[i^1].w+=w;ret+=w;if(ret==maxf)break;}}if(!ret)level[u]=-1;//优化,防止重搜,说明u这一路不可能有流量了 return ret;
}
ll Dinic(int s,int t)
{ll ans=0;while(bfs(s,t))ans+=dfs(s,INF,t);return ans;
}
int main()
{ scanf("%d",&t);//n个点 m条边 while(t--){scanf("%d%d",&n,&m);init(2*n+2);ss=2*n+1,ee=2*n+2;for(int j=0;j<m;++j) {int u,v;scanf("%d%d",&u,&v);add2(u,v+n,INF,1);}for(int j=1;j<=n;++j){add2(ss,j,1,1);add2(j+n,j,INF,1);add2(j+n,ee,1,1);}ll ans=Dinic(ss,ee);printf("%lld\n",n-ans);}return 0;
}

这篇关于2018年长沙理工大学第十三届程序设计竞赛 K. zzq的离散数学教室2(dilworth定理+有向图可相交路径覆盖 dinic版)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/896302

相关文章

Linux修改pip和conda缓存路径的几种方法

《Linux修改pip和conda缓存路径的几种方法》在Python生态中,pip和conda是两种常见的软件包管理工具,它们在安装、更新和卸载软件包时都会使用缓存来提高效率,适当地修改它们的缓存路径... 目录一、pip 和 conda 的缓存机制1. pip 的缓存机制默认缓存路径2. conda 的缓

Windows系统下如何查找JDK的安装路径

《Windows系统下如何查找JDK的安装路径》:本文主要介绍Windows系统下如何查找JDK的安装路径,文中介绍了三种方法,分别是通过命令行检查、使用verbose选项查找jre目录、以及查看... 目录一、确认是否安装了JDK二、查找路径三、另外一种方式如果很久之前安装了JDK,或者在别人的电脑上,想

Python中Windows和macOS文件路径格式不一致的解决方法

《Python中Windows和macOS文件路径格式不一致的解决方法》在Python中,Windows和macOS的文件路径字符串格式不一致主要体现在路径分隔符上,这种差异可能导致跨平台代码在处理文... 目录方法 1:使用 os.path 模块方法 2:使用 pathlib 模块(推荐)方法 3:统一使

一文教你解决Python不支持中文路径的问题

《一文教你解决Python不支持中文路径的问题》Python是一种广泛使用的高级编程语言,然而在处理包含中文字符的文件路径时,Python有时会表现出一些不友好的行为,下面小编就来为大家介绍一下具体的... 目录问题背景解决方案1. 设置正确的文件编码2. 使用pathlib模块3. 转换路径为Unicod

MySQL9.0默认路径安装下重置root密码

《MySQL9.0默认路径安装下重置root密码》本文主要介绍了MySQL9.0默认路径安装下重置root密码,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们... 目录问题描述环境描述解决方法正常模式下修改密码报错原因问题描述mysqlChina编程采用默认安装路径,

Java覆盖第三方jar包中的某一个类的实现方法

《Java覆盖第三方jar包中的某一个类的实现方法》在我们日常的开发中,经常需要使用第三方的jar包,有时候我们会发现第三方的jar包中的某一个类有问题,或者我们需要定制化修改其中的逻辑,那么应该如何... 目录一、需求描述二、示例描述三、操作步骤四、验证结果五、实现原理一、需求描述需求描述如下:需要在

vue解决子组件样式覆盖问题scoped deep

《vue解决子组件样式覆盖问题scopeddeep》文章主要介绍了在Vue项目中处理全局样式和局部样式的方法,包括使用scoped属性和深度选择器(/deep/)来覆盖子组件的样式,作者建议所有组件... 目录前言scoped分析deep分析使用总结所有组件必须加scoped父组件覆盖子组件使用deep前言

Python绘制土地利用和土地覆盖类型图示例详解

《Python绘制土地利用和土地覆盖类型图示例详解》本文介绍了如何使用Python绘制土地利用和土地覆盖类型图,并提供了详细的代码示例,通过安装所需的库,准备地理数据,使用geopandas和matp... 目录一、所需库的安装二、数据准备三、绘制土地利用和土地覆盖类型图四、代码解释五、其他可视化形式1.

python获取当前文件和目录路径的方法详解

《python获取当前文件和目录路径的方法详解》:本文主要介绍Python中获取当前文件路径和目录的方法,包括使用__file__关键字、os.path.abspath、os.path.realp... 目录1、获取当前文件路径2、获取当前文件所在目录3、os.path.abspath和os.path.re

hdu2544(单源最短路径)

模板题: //题意:求1到n的最短路径,模板题#include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#i