网站建设好后 如何验收,什么网站可以做护考题,网站建设类外文翻译,网络营销意思题目 Description “那么真的有果尔德施坦因这样一个人?”他问道。 “是啊#xff0c;有这样一个人#xff0c;他还活着。至于在哪里#xff0c;我就不知道了。” “那么那个密谋——那个组织?这是真的吗?不是秘密警察的捏造吧?” “不是#xff0c;这是真的。我们管… 题目 Description “那么真的有果尔德施坦因这样一个人?”他问道。 “是啊有这样一个人他还活着。至于在哪里我就不知道了。” “那么那个密谋——那个组织?这是真的吗?不是秘密警察的捏造吧?” “不是这是真的。我们管它叫兄弟会。除了它确实存在你们是它的会员以外你们 就别想知道别的了。” 他知道的是这种思想一定会一代一代地传下去他们一定能够在没有黑暗的地方再会。 他不知道的是兄弟会已经走到了崩溃的边缘思想警察早已无孔不入那没有黑暗的地方 是友爱部是 101 室…… 兄弟会的头目之一爱麦虞埃尔•果尔德施坦因正在谋划着一场无力的反抗。这抗争的内容竟是一场宏大的舞会。这作为小资情调、腐朽没落的代表以及未经允许的群众运动 是大洋国严格禁止的甚至是 crimethink这也是为了加强组织的团结并且为那终将到来的最后一战而激励、鼓舞士气。 众所周知兄弟会为了避免思想警察的追捕保密措施相当严密。会内一位高级干部奥勃良如此说“从你们切身经验来说你们永远连十来个会员也不认识。”注意测试数据可能不符合这句话具体来说每个人只认识他的全部上司。一个人的上司要么是他的直接上司 在输入中会向你给出并且可能不止一人要么是这个人的某个上司的直接上司。为了增进同志之间的感情同时为了防止渗入兄弟会的间谍破获整个组织的组成与结构果尔德 施坦因想要确保在舞会中任意两个人都互不相识。 真理部的外围党员温斯顿在奥勃良的介绍下加入了兄弟会。他刚刚知道了这个激动人心的舞 会仿佛又感受到了那若有若无的、来自旧时代的温暖。因为参与舞会的人越多他与他亲爱的裘莉亚就越有可能重逢所以他很好奇最多能有多少人参与。 Input 第一行两个正整数 NM表示兄弟会的会员人数以及关系数。然后 M 行每行 2 个正整数 x,y1x,yN,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%数据满足 n5。 对于 20%数据满足 n20。 对于另 10%数据满足会员构成一棵外向树即除了一号会员即果尔德施坦因本人之外的每个会员恰好只有一个上司且一号会员没有上司。 对于另 10%数据满足会员构成一颗内向树即除了一号会员即温斯顿之外的每个会员恰好只有一个直接下属且一号会员没有下属。 对于另 30%数据满足每个会员要么没有上司要么没有下属。 对于 100%数据满足 n200关系不会重复出现且不会自相矛盾即 A 既是 B 的上司也是 B 的下属。换句话说关系构成了一张无重边的有向无环图。保证图联通。 做法 显然这是一个有向无环图。 对于每一条有向边(u,v)(u,v)表示vv是uu的的上司。 题目要让我们在图上找到尽量多的点使得这些点不能互相到达。 咋做 题解上这样说 在有向无环图中我们定义 链图上一些点的集合对于链上任意两个点 x、y满足 x 能到达 y 或者 y 能到达 x。 反链图上一些点的的集合对于反链上任意两个点 x、y满足 x 不能到达 y 并且 y 不能到达 x。 所以就是很显然的求最长反链长度了~ 有以下 Dilworth 定理 最长反链长度最小链覆盖选取最少的链覆盖所有的点 这是题解上话然后我上网找这条定理的证明结果……证明很少并且好几篇博客是一个样子而且让我一脸懵逼甚至感觉那证明还是错的…… 于是只能感性理解。 假设用一些链来覆盖整张图。 对于每个反链上的点它们各自在一条链上。 如果这些链的数量大于最小链覆盖那么多出来的那些都是废的会出现两个反链上的点能连通与题目不符…… 好吧感性理解这种东西是不方便用语言来说的。 现在假设我们已经知道了这个定理。 接下来可以用二分图匹配来解决 将每个点拆成左右两边实现时不需要。 对于一条边(u,v)(u,v)就在二分图上uleftuleft和vrightvright连一条有向边。 跑一遍二分图匹配那么答案就是n−最大匹配数n−最大匹配数。 Why? 在二分图连一条边可以视为将两条链合并也就是将最小链覆盖数−1−1。 拆成二分图避免路径相交的问题。 代码 using namespace std;
#include cstdio
#include cstring
#include algorithm
#define MAXN 200
int n,m;
bool to[MAXN1][MAXN1];//表示是否连通
int be[MAXN*21];
bool vis[MAXN1];
bool matching(int);
int main(){freopen(dance.in,r,stdin);freopen(dance.out,w,stdout);scanf(%d%d,n,m);for (int i1;im;i){int u,v;scanf(%d%d,u,v);to[v][u]1;}//要用Floyed来处理处连通性for (int k1;kn;k)for (int i1;in;i)for (int j1;jn;j)to[i][j]|to[i][k]to[k][j]; int max_matching0;for (int i1;in;i){memset(vis,0,sizeof vis);if (matching(i))max_matching;}printf(%d\n,n-max_matching);return 0;
}
bool matching(int x){for (int i1;in;i)if (to[x][i] !vis[i]){vis[i]1;if (!be[i] || matching(be[i])){be[i]x;return 1;}}return 0;
} 总结 这题好打是好打就是理解得迷迷糊糊的。 感性理解还是很重要的…… 转载于:https://www.cnblogs.com/jz-597/p/11145275.html
