2006年4月4日  8:00  P.M [img]ProblemImg/P1184_conan.jpg[/img][img]ProblemImg/P1184_ai.jpg[/img] 在这春暖花开,  阳光明媚的日子里,  柯南在”高效信息学在线评测系统”Vijos上切题目,  他兴高采烈的将刚刚拍完的程序提交上去,  突然发现前面排起了长长的队伍,  好多人在waiting,  又过一会,  Vijos崩溃. [img]ProblemImg/P1184_waiting.jpg[/img] 柯南很快意识到这不是一个普通平常的,  Vijos时常发生的系统不稳定现象,  而是一场有预谋的案件.  他找到Vivian  Snow  (16周岁). -------> [img]ProblemImg/P1184_viviansnow.jpg[/img]（偶偷偷的说，这像不像喝了Aptx的Vvs？^_^） [b]Vivian  Snow抱怨说[/b]:”  已经是第二次了,  什么世道啊,  看我牛不顺眼啊!!”  [b]柯南(`_`)问[/b]:”  那么你当时记录下访问Vijos服务器的IP地址了么?”  [b]Vivian  Snow[/b]:”  这是自然的,  我把当时的记录拿给你看.” 柯南扫了一眼,  发现当时访问Vijos的众多IP中,  有一部分IP,  重复大量的向服务器投了巨大的数据包.  他意识到,  很可能是这些包将服务器挤爆的.  这种不算高明的手法居然把Vijos弄瘫痪了,  而攻击者很显然留下了大量证据,  只要追寻这些IP就可以了. [b]灰原哀忽然出现了[/b]:”  江户川柯南,  你想得还真简单呢.” [b]柯南[/b]:”  难道……  难道你也在切Vijos……” [b]小哀[/b]:”  现在没必要讨论这个了,  关键是攻击者很可能没用真实IP  .” [b]柯南[/b]:”  Er……  “ [b]柯南沉默良久,  之后缓缓站起身来[/b]:”  如果我的推理没有错的话,  我们把访问过Vijos的IP地址调查一下,  找出当时它和哪些IP联络过,  筛选出向Vijos投过包的IP.    底下只考虑向Vijos投过包的IP,  对于两个直接联络过的IP,  他们发送的所有包的大小相加,  作为联络代价.  假定两个IP如果没有直接联络,  可以通过中间IP进行联络,  联络路径代价为联络路径中各段联络代价总和.  两个IP的联络代价为各条联络路径代价中最小的那个.  找出某一个投放过包IP地址使他与其他投放过包的IP联络代价总和最大,  那么这个IP地址就是攻击者的IP了.” [b]小哀[/b]:”  你这个小迷糊还真不赖嘛,  可是你是怎样推理出的,  还有你怎么找出其他IP是否联络过呢？” [b]柯南[/b]:”  我也不知道,  Thunder叫我这么说的,  他说不这么说这题没法出了.  至于IP之间的联络情况,  Thunder说他已经放在证据里了.” [b]小哀[/b]:”  那么,  我去调查当时访问过Vijos的IP,  筛选出有嫌疑的.” [b]柯南[/b]:”  等等,  话是这么说,  可是数据这么大……..” [b]小哀[/b]:”  原来你也有犯难的时候,  你难道没发现有位大牛看我们对话很久了么.” [b]画外音[/b]:”  那么就请看题的这位大牛帮助解决柯南的难题.”

第一行&nbsp 一个正整数N&nbsp (N≤100000)
第2~N+1行,&nbsp 每行一个IP地址&nbsp 和一个正的整型数表示某个IP地址投放的包的大小
注意同一IP地址可能投放多次包,&nbsp 至多不超过2000个IP地址
第N+2行&nbsp 一个正整数M(M≤100000)
第N+3~M+N+2行,&nbsp 每行两个IP地址用空格隔开,&nbsp 表示两个IP地址之间有过联络,
不会出现两个IP多次联络的情况,&nbsp 但会有IP访问2~N+1行未出现过IP的情况.

一行&nbsp
The_ONLY_truth_is:_it_is_you,_攻击者的IP地址&nbsp &nbsp &nbsp (注：_为空格)
如果存在两个或以上的IP地址到其他IP的代价总和最大,&nbsp 或者不能访问到其他所有投放包的IP,&nbsp 那么认为攻击者无法确定,&nbsp 则将攻击者的IP地址作为222.240.168.135处理

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
 \n
            · \n
            · \n
             · \n
             · \n
 \n
            ·            \n
            ·             \n
            ·             \n
            ·             \n
            ·           \n

The ONLY truth is: it is you, 60.191.255.98
   ·    ·     ·   ·  ·  ·    ·             \n

结局
最终,&nbsp 攻击者被追查到了,&nbsp 他居然是OIBH组织成员Gengar大牛.
Gengar被捕后的独白:”&nbsp 曾经我沉迷于切Vijos,&nbsp 但是每每我看到一个好题,&nbsp 把它拍完,&nbsp 提交的时候,&nbsp 都看到了waiting长龙.&nbsp 于是,&nbsp 我下定决心,&nbsp 既然Vijos不让我AC,&nbsp 我就将Vijos毁灭.&nbsp 后来,&nbsp 我发现一个包可以引发一连串waiting,&nbsp 十个包就是十连串,&nbsp 一百万个包就足以使Vijos毁灭,&nbsp 我的目的也就达成了.&nbsp 小弟弟,&nbsp 送你个包？”
可是无论如何逼供Gengar大牛对于组织内幕一概不招,&nbsp 而Gengar大牛的机房也早已被组织处理.&nbsp 柯南再一次和组织擦肩而过,&nbsp 命运之轮继续旋转………