大家好,又见面了,我是你们的朋友全栈君。
Description
“那么真的有果尔德施坦因这样一个人?”他问道。
“是啊,有这样一个人,他还活着。至于在哪里,我就不知道了。”
“那么那个密谋——那个组织?这是真的吗?不是秘密警察的捏造吧?”
“不是,这是真的。我们管它叫兄弟会。除了它确实存在,你们是它的会员以外,你们 就别想知道别的了。”
他知道的是,这种思想一定会一代一代地传下去,他们一定能够在没有黑暗的地方再会。
他不知道的是,兄弟会已经走到了崩溃的边缘;思想警察早已无孔不入;那没有黑暗的地方, 是友爱部,是 101 室……
兄弟会的头目之一,爱麦虞埃尔•果尔德施坦因,正在谋划着一场无力的反抗。这抗争的内容,竟是一场宏大的舞会。(这作为小资情调、腐朽没落的代表,以及未经允许的群众运动, 是大洋国严格禁止的(甚至是 crimethink))这也是为了加强组织的团结,并且为那终将到来的最后一战而激励、鼓舞士气。
众所周知,兄弟会为了避免思想警察的追捕,保密措施相当严密。会内一位高级干部奥勃良如此说:“从你们切身经验来说,你们永远连十来个会员也不认识。”(注意:测试数据可能不符合这句话)具体来说,每个人只认识他的全部上司。一个人的上司要么是他的直接上司
(在输入中会向你给出,并且可能不止一人),要么是这个人的某个上司的直接上司。为了增进同志之间的感情,同时为了防止渗入兄弟会的间谍破获整个组织的组成与结构,果尔德 施坦因想要确保在舞会中任意两个人都互不相识。
真理部的外围党员温斯顿在奥勃良的介绍下加入了兄弟会。他刚刚知道了这个激动人心的舞 会,仿佛又感受到了那若有若无的、来自旧时代的温暖。因为参与舞会的人越多,他与他亲爱的裘莉亚就越有可能重逢,所以他很好奇最多能有多少人参与。
Input
Output
Sample Input
4 4 1 2 2 4 1 3 3 4
Sample Output
2
Data Constraint
对于 20%数据,满足 n<=20。
对于另 10%数据,满足会员构成一棵外向树,即:除了一号会员(即果尔德施坦因本人)之外的每个会员,恰好只有一个上司,且一号会员没有上司。
对于另 10%数据,满足会员构成一颗内向树,即:除了一号会员(即温斯顿)之外的每个会员,恰好只有一个直接下属,且一号会员没有下属。
对于另 30%数据,满足每个会员要么没有上司,要么没有下属。
对于 100%数据,满足 n<=200,关系不会重复出现,且不会自相矛盾(即 A 既是 B 的上司也是 B 的下属)。换句话说,关系构成了一张无重边的有向无环图。保证图联通。
分析
这题我们发现是一个最长反链长度
那么根据dilworth原理
最长反链长度=最小链覆盖
那么向x到y连通的点对(x,y)连边,跑二分图
则最小链覆盖=原图点数n-二分图匹配数
连通性问题用floyd再+二分图就行
#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账号...