PoppinC天涯歌女版本_floyd warshall算法

PoppinC天涯歌女版本_floyd warshall算法[二分图][floyd]JZOJ 5857 没有上司的舞会

大家好,又见面了,我是你们的朋友全栈君。

Description


“那么真的有果尔德施坦因这样一个人?”他问道。

“是啊,有这样一个人,他还活着。至于在哪里,我就不知道了。”

“那么那个密谋——那个组织?这是真的吗?不是秘密警察的捏造吧?”

“不是,这是真的。我们管它叫兄弟会。除了它确实存在,你们是它的会员以外,你们  就别想知道别的了。”

 

他知道的是,这种思想一定会一代一代地传下去,他们一定能够在没有黑暗的地方再会。

 

他不知道的是,兄弟会已经走到了崩溃的边缘;思想警察早已无孔不入;那没有黑暗的地方,   是友爱部,是 101 室……

兄弟会的头目之一,爱麦虞埃尔•果尔德施坦因,正在谋划着一场无力的反抗。这抗争的内容,竟是一场宏大的舞会。(这作为小资情调、腐朽没落的代表,以及未经允许的群众运动, 是大洋国严格禁止的(甚至是 crimethink))这也是为了加强组织的团结,并且为那终将到来的最后一战而激励、鼓舞士气。

众所周知,兄弟会为了避免思想警察的追捕,保密措施相当严密。会内一位高级干部奥勃良如此说:“从你们切身经验来说,你们永远连十来个会员也不认识。”(注意:测试数据可能不符合这句话)具体来说,每个人只认识他的全部上司。一个人的上司要么是他的直接上司

(在输入中会向你给出,并且可能不止一人),要么是这个人的某个上司的直接上司。为了增进同志之间的感情,同时为了防止渗入兄弟会的间谍破获整个组织的组成与结构,果尔德   施坦因想要确保在舞会中任意两个人都互不相识。

真理部的外围党员温斯顿在奥勃良的介绍下加入了兄弟会。他刚刚知道了这个激动人心的舞   会,仿佛又感受到了那若有若无的、来自旧时代的温暖。因为参与舞会的人越多,他与他亲爱的裘莉亚就越有可能重逢,所以他很好奇最多能有多少人参与。

 

 

Input

第一行两个正整数 N,M,表示兄弟会的会员人数以及关系数。然后 M 行,每行 2 个正整数 x,y(1<=x,y<=N,x≠y),表示 x 是 y 的直接上司(即 y 是 x 的直接下属)。

 

 

Output

输出一行一个整数,表示参加舞会的最多人数。

 

 

 

Sample Input

4 4
1 2
2 4
1 3
3 4
 

Sample Output

2
 

 

Data Constraint

对于 5%数据,满足 n<=5。

对于 20%数据,满足 n<=20。

对于另 10%数据,满足会员构成一棵外向树,即:除了一号会员(即果尔德施坦因本人)之外的每个会员,恰好只有一个上司,且一号会员没有上司。

对于另 10%数据,满足会员构成一颗内向树,即:除了一号会员(即温斯顿)之外的每个会员,恰好只有一个直接下属,且一号会员没有下属。

对于另 30%数据,满足每个会员要么没有上司,要么没有下属。

对于 100%数据,满足 n<=200,关系不会重复出现,且不会自相矛盾(即 A 既是 B 的上司也是 B 的下属)。换句话说,关系构成了一张无重边的有向无环图。保证图联通。

分析

这题我们发现是一个最长反链长度

那么根据dilworth原理

最长反链长度=最小链覆盖

那么向x到y连通的点对(x,y)连边,跑二分图

则最小链覆盖=原图点数n-二分图匹配数

连通性问题用floyd再+二分图就行

PoppinC天涯歌女版本_floyd warshall算法
PoppinC天涯歌女版本_floyd warshall算法

#include <iostream>
#include <cstdio>
#include <memory.h>
using namespace std;
const int N=201;
bool g[N][N],cs[N];
int p[N];
int n,m;

void Floyd() {
    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][k]&g[k][j]);
}

bool Find(int st) {
    for (int i=1;i<=n;i++)
        if (g[st][i]&&!cs[i]) {
            cs[i]=1;
            if (!p[i]||Find(p[i])) {
                p[i]=st;
                return 1;
            }
        }
    return 0;
}

int main() {
    freopen("dance.in","r",stdin);
    freopen("dance.out","w",stdout);
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++) {
        int u,v;
        scanf("%d%d",&u,&v);
        g[u][v]=1;
    }
    Floyd();
    int ans=n;
    for (int i=1;i<=n;i++) {
        memset(cs,0,sizeof cs);
        if (Find(i)) ans--;
    }
    printf("%d",ans);
}

View Code

 

转载于:https://www.cnblogs.com/mastervan/p/9623302.html

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/107319.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • 微信小程序反编译教程_微信小程序防止反编译

    微信小程序反编译教程_微信小程序防止反编译最近写爬虫需要小程序反编译,过程总结下…..通过微信PC版,打开需要反编译的小程序,小程序将产生缓存文件(但他是加密的),通过”小程序解密包”工具将加密的缓存文件解密成为”XXX.wxapkg”文件然后通过wxappunpacker工具反编译下载地址:链接:https://pan.baidu.com/s/1nqg97PxkFTt1TnEWECikYQ提取码:bsu91.找到小程序加密文件微信PC版查看设置->文件管理->打开文件夹然后往上一层返回一步例如:………

  • JAVA设计模式初探之装饰者模式

    这个模式花费了挺长时间,开始有点难理解,其实就是定义:动态给一个对象添加一些额外的职责,就象在墙上刷油漆.使用Decorator模式相比用生成子类方式达到功能的扩充显得更为灵活。设计初衷:通常可以使用继承来实现功能的拓展,如果这些需要拓展的功能的种类很繁多,那么势必生成很多子类,增加系统的复杂性,同时,使用继承实现功能拓展,我们必须可预见这些拓展功能,这些功能是编译时就确定了,是静态的。…

  • 常用链表排序算法_单链表的排序算法

    常用链表排序算法_单链表的排序算法转载自:http://blog.csdn.net/northplayboy/article/details/552388  ========================== 功能:选择排序(由小到大) 返回:指向链表表头的指针==========================*//* 选择排序的基本思想就是反复从还未排好序的那些节点中, 选出键值(就是

    2022年10月11日
  • sql聚合函数的使用「建议收藏」

    sql聚合函数的使用「建议收藏」1.selectcount(*)fromtable;这个是统计查询出来的数据数量2.selectmin(id)fromtable;取出数据中id最小的值3.selectmax(id)fromtable;取出数据中id最大的值4.selectMOD(125,10);取余数5.selectfloor(columns)fromtablewherecondition;从取出的数据中向下取整,比如你取到的数据是45.8,那么通过floor函数处理之后,打印出来的就是4

  • 二级指针动态数组,模拟指针数组

    二级指针动态数组,模拟指针数组

  • 常见电容器图片_电容分类图片-各种电容器图片[通俗易懂]

    常见电容器图片_电容分类图片-各种电容器图片[通俗易懂]《电容分类图片-各种电容器图片》由会员分享,可在线阅读,更多相关《电容分类图片-各种电容器图片(7页珍藏版)》请在人人文库网上搜索。1、电容分类图片-各种电容器图片第1幅图1胆电容。图2灯具电容器。图3MKPH电容。图4MET电容。图5,10PEI电容,图6,胆贴片电容。图7MPE电容。图8贴片电容。图11轴向电解电容器。图12MPP电容第2幅图1PPN电容。图2PET电容…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号