HBC232792[JSOI2010]GROUP 部落划分 GROUP,二分,并查集,生成树,图论,数据结构,分治模拟人生2077题解

冷默言语算法基础篇 2023-11-19 00:02:01 102 0

全网最全C++题库，助您快速提升编程技能！题库丰富多样，涵盖各个领域，让您在练习中不断成长！

n 个国家，它们互相之间都有或大或小的矛盾，为了缓和矛盾，两个国家之间需要找到一个调解国，Kanade 定义不可信度为一国调解双方矛盾机率之差的绝对值，因为这个绝对值越大，越容易导致强国对弱国的剥削，Kanade 想知道，对于一次调解的所有情况来说，最小的不可信度和最大的不可信度分别有多大。

Kanade 最近在玩模拟人生 2077。这是一款模拟经营类游戏，她在这个游戏中的身份是某国的外交官。今天她的任务是快速分析目前国际形势。目前有 n n 个国家，它们互相之间都有或大或小的矛盾，为了缓和矛盾，两个国家之间需要找到一个调解国。 Kanade 利用国家的综合国力和外交能力评估调解的有效性。根据每个国家发展情况与国际地位的不同，Kanade 用一个整数去评价每个国家的综合国力和外交能力。对于一次调解，定义与被调解国的国力差为被调解国与调解国的国力差，与被调解国的外交能力差为被调解国与调解国的外交能力差，则调解成功一方的机率就等于本国与一方的国力差乘以本国与另一方的外交能力差。 Kanade 定义不可信度为一国调解双方矛盾机率之差的绝对值，因为这个绝对值越大，越容易导致强国对弱国的剥削。Kanade 想知道，对于一次调解的所有情况来说，最小的不可信度和最大的不可信度分别有多大。