传送门 这题其实有两种做法： 1.1.1. 我一开始想到的是二分加并查集，考虑二分最近部落的距离，如果两点iii，jjj距离小于等于midmidmid那么连边，并查集维护，最后统计有多少集合。 考虑如何证明单调性：如果两点iii，jjj在mid1mid1mid1情况下能连边，那么在mid2mid2mid2情况下也能连边（mid2>mid1mid2>mid1mid2>mid1...

传送门 题意：求最大团，团是一个点的集合，其中任意两点都有边相连。 最大团属于NPCNPCNPC问题None Player Characters 虽然数据范围小，n≤50n \le 50n≤50，但是直接暴搜肯定超时。 考虑随机化，每次打乱点的总集合SSS 从SSS中取出点vvv，若vvv与AnsAnsAns中的所有点都有边相连，则将vvv加入AnsAnsAns，否则跳过vvv 实践证明随机...

传送门 考虑建图，把xxx方向zzz方向距离都不超过222的点连一条边长为111的边，最后跑一遍SPFA。 具体实现可以把点放进一个mapmapmap里面。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636...

我们把自己建了水库的节点称为AAA类节点，通过其他农田饮水的称为BBB类节点。 考虑最后生成的图，根据贪心，图中肯定没有环，所以这个图是一个森林，且森林中的每棵树都有且仅有一个AAA类节点，若大于111则造成浪费。 考虑把森林变成树，我们建立超级源点000号节点，和图中每个节点iii相连，边权就可以设为wiw_iwi​， 然后节点iii，节点jjj连边权为pijp_{ij}pij​的边即可。...

传送门 答案上界为该无向图中的偶点数量，考虑构造方案达到这个上界 建一个虚点S向所有奇点连边，这样奇点都变成了偶点，而奇点的个数一定是偶数，故S也是个偶点 于是新图存在欧拉回路，根据这个对边进行定向，则原图中所有偶点入度等于出度，达到上界 12345678910111213141516171819202122232425262728293031323334353637383940414243...