CoVH之华丽的IP伪装
测试数据来自 system/1184
背景
挡在面前的铜墙铁壁
只要换一种思考方式也许就能变成一扇大门
唯一看穿真相的是一个看似小孩
智慧却过于常人的
他的名字就是名侦探柯南
描述
2006年4月4日 8:00 P.M
在这春暖花开, 阳光明媚的日子里, 柯南在”高效信息学在线评测系统”Vijos上切题目, 他兴高采烈的将刚刚拍完的程序提交上去, 突然发现前面排起了长长的队伍, 好多人在waiting, 又过一会, Vijos崩溃.
柯南很快意识到这不是一个普通平常的, Vijos时常发生的系统不稳定现象, 而是一场有预谋的案件. 他找到Vivian Snow (16周岁).
------->
Vivian Snow抱怨说:“已经是第二次了, 什么世道啊, 看我牛不顺眼啊!!”
柯南(`_`)问:“那么你当时记录下访问Vijos服务器的IP地址了么?”
Vivian Snow:“这是自然的, 我把当时的记录拿给你看.”
柯南扫了一眼, 发现当时访问Vijos的众多IP中, 有一部分IP, 重复大量的向服务器投了巨大的数据包. 他意识到, 很可能是这些包将服务器挤爆的. 这种不算高明的手法居然把Vijos弄瘫痪了, 而攻击者很显然留下了大量证据, 只要追寻这些IP就可以了.
灰原哀忽然出现了:“江户川柯南, 你想得还真简单呢.”
柯南:“难道…… 难道你也在切Vijos……”
小哀:“现在没必要讨论这个了, 关键是攻击者很可能没用真实IP .”
柯南:“Er…… “
柯南沉默良久, 之后缓缓站起身来:“如果我的推理没有错的话, 我们把访问过Vijos的IP地址调查一下, 找出当时它和哪些IP联络过, 筛选出向Vijos投过包的IP. 底下只考虑向Vijos投过包的IP, 对于两个直接联络过的IP, 他们发送的所有包的大小相加, 作为联络代价. 假定两个IP如果没有直接联络, 可以通过中间IP进行联络, 联络路径代价为联络路径中各段联络代价总和. 两个IP的联络代价为各条联络路径代价中最小的那个. 找出某一个投放过包IP地址使他与其他投放过包的IP联络代价总和最大, 那么这个IP地址就是攻击者的IP了.”
小哀:“你这个小迷糊还真不赖嘛, 可是你是怎样推理出的, 还有你怎么找出其他IP是否联络过呢？”
柯南:“我也不知道, Thunder叫我这么说的, 他说不这么说这题没法出了. 至于IP之间的联络情况, Thunder说他已经放在证据里了.”
小哀:“那么, 我去调查当时访问过Vijos的IP, 筛选出有嫌疑的.”
柯南:“等等, 话是这么说, 可是数据这么大……..”
小哀:“原来你也有犯难的时候, 你难道没发现有位大牛看我们对话很久了么.”
画外音:“那么就请看题的这位大牛帮助解决柯南的难题.”
格式
输入格式
第一行 一个正整数N (N≤100000)
第2~N+1行, 每行一个IP地址 和一个正的整型数表示某个IP地址投放的包的大小
注意同一IP地址可能投放多次包, 至多不超过2000个IP地址
第N+2行 一个正整数M(M≤100000)
第N+3~M+N+2行, 每行两个IP地址用空格隔开, 表示两个IP地址之间有过联络,
不会出现两个IP多次联络的情况, 但会有IP访问2~N+1行未出现过IP的情况.
输出格式
一行
The_ONLY_truth_is:_it_is_you,_攻击者的IP地址 (注：_为空格)
如果存在两个或以上的IP地址到其他IP的代价总和最大, 或者不能访问到其他所有投放包的IP, 那么认为攻击者无法确定, 则将攻击者的IP地址作为222.240.168.135处理
样例1
样例输入1
4
222.134.7.28 7
61.74.218.22 8
60.191.255.98 4
219.153.2.168 5
5
222.134.7.28 61.74.218.22
222.134.7.28 60.191.255.98
222.134.7.28 219.153.2.168
61.74.218.22 219.153.2.168
222.134.7.28 213.87.4.23
样例输出1
The ONLY truth is: it is you, 60.191.255.98
限制
共10点，全部限时1秒
提示
结局
最终, 攻击者被追查到了, 他居然是OIBH组织成员Gengar大牛.
Gengar被捕后的独白:” 曾经我沉迷于切Vijos, 但是每每我看到一个好题, 把它拍完, 提交的时候, 都看到了waiting长龙. 于是, 我下定决心, 既然Vijos不让我AC, 我就将Vijos毁灭. 后来, 我发现一个包可以引发一连串waiting, 十个包就是十连串, 一百万个包就足以使Vijos毁灭, 我的目的也就达成了. 小弟弟, 送你个包？”
可是无论如何逼供Gengar大牛对于组织内幕一概不招, 而Gengar大牛的机房也早已被组织处理. 柯南再一次和组织擦肩而过, 命运之轮继续旋转………
