AtCoder ABC139E League 判dag dag上简单dp
最新推荐文章于 2022-08-29 01:04:29 发布
原创
最新推荐文章于 2022-08-29 01:04:29 发布
·
513 阅读
·
0
·
1
·
CC 4.0 BY-SA版权
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
该博客讨论了一个涉及n个人的比赛调度问题，每个人都预设了与其他n-1人的比赛顺序。问题要求判断是否存在一种比赛日程安排能符合所有人的期望，同时确定最少需要多少天完成所有比赛。若图是无环定向图（DAG），则可能存在解决方案，其中DAG的最长路径代表所需的最多天数。博客提到了判断DAG的O(N+V)算法和求DAG最长路的简单DP方法，同样也是O(N+V)的时间复杂度。
有n(1000)n(1000)n(1000)个人, 每个人都要和其他n−1n-1n−1个人进行比赛, 每个人都规定了他参加的n−1n-1n−1场比赛的顺序, 问是否有一种比赛顺序能满足所有人心意. 此外, 每天可以安排多场比赛,但每天一个人只能参加一场比赛. 如果不能满足所有人的心意输出−1-1−1, 如果能够满足所有人心意, 那么输出最少需要比赛多少天.
设[A,B][A,B][A,B]代表AAA和BBB两个人进行的那场比赛. 可以把[A,B][A,B][A,B]当作一个点, 那么题目给出的关系矩阵就会构成一个有关每场[比赛][比赛]