酷暑一夏1

不忘初心,方得始终


Vijos1203 CoVH之华丽的IP伪装 题解

题目核心部分

(没用的背景已省略,挺有趣的可以去看原题)
如果我的推理没有错的话, 我们把访问过Vijos的IP地址调查一下, 找出当时它和哪些IP联络过, 筛选出向Vijos投过包的IP. 底下只考虑向Vijos投过包的IP, 对于两个直接联络过的IP, 他们发送的所有包的大小相加, 作为联络代价. 假定两个IP如果没有直接联络, 可以通过中间IP进行联络, 联络路径代价为联络路径中各段联络代价总和. 两个IP的联络代价为各条联络路径代价中最小的那个. 找出某一个投放过包IP地址使他与其他投放过包的IP联络代价总和最大, 那么这个IP地址就是攻击者的IP了。

题解

将IP映射为节点编号,SPFA即可,SPFA求的是最短路径,最后取所有(各次SPFA)dis中的最大值。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include<cstdio>
#include<map>
#include<string>
#include<climits>
#include<queue>
#include<iostream>
#include<cstring>
const int MAXN=2000+5;
const int MAXM=200000+5;
struct Edge{int u,v,next,w;};
std::map<std::string,int>map;
Edge edge[MAXM];int nodecnt,cnt,head[MAXN],dis[MAXN],wei[MAXN];std::string unmap[MAXN];bool vis[MAXN];
std::queue<int>que;
void AddEdge(int u,int v,int w)
{
int &i=++cnt;
edge[i].u=u;edge[i].v=v;edge[i].w=w;
edge[i].next=head[u];head[u]=i;
}
int SPFA(int begin)
{
for(int i=1;i<=nodecnt;i++)
dis[i]=INT_MAX;
dis[begin]=0;
memset(vis,0,sizeof(vis));
que.push(begin);
while(!que.empty())
{
int u=que.front();que.pop();
vis[u]=0;
for(int i=head[u];i;i=edge[i].next)
{
int v=edge[i].v;
if(dis[v]>dis[u]+edge[i].w)
{
dis[v]=dis[u]+edge[i].w;
if(!vis[v])
{
vis[v]=1;
que.push(v);
}
}
}
}
int ans=0;
for(int i=1;i<=nodecnt;i++)
{
if(dis[i]==INT_MAX) return INT_MAX; else ans+=dis[i];
}
return ans;
}
int main()
{
int n,a,b,c;std::string inp;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
std::cin>>inp;
std::cin>>b;
a=map[inp];
if(!a)
{
map[inp]=++nodecnt;
unmap[nodecnt]=inp;
a=nodecnt;
}
wei[a]+=b;
}
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
std::cin>>inp;
a=map[inp];
if(!a) continue;
std::cin>>inp;
b=map[inp];
if(!b) continue;
c=wei[a]+wei[b];
AddEdge(a,b,c);
AddEdge(b,a,c);
}
int r1=0,r2=0;int id;
for(int i=1;i<=nodecnt;i++)
{
c=SPFA(i);
if(c==INT_MAX) goto err;
if(r1<c) {r1=c;id=i;continue;}
if(r2<c) r2=c;
}
if(r1==r2) goto err;
printf("The ONLY truth is: it is you, ");
std::cout<<unmap[id];
return 0;
err:
printf("The ONLY truth is: it is you, 222.240.168.135");
return 0;
}
最近的文章

Vijos1415 魔族密码 题解

题目核心部分魔族现在使用一种新型的密码系统。每一个密码都是一个给定的仅包含小写字母的英文单词表,每个单词至少包含1个字母,至多75个字母。如果在一个由一个词或多个词组成的表中,除了最后一个以外,每个单词都被其后的一个单词所包含,即前一个单词是后一个单词的前缀,则称词表为一个词链。例如下面单词组成了一 …

于  Vijos 继续阅读
更早的文章

Vijos1203 CoVH之资料页数 题解

题目柯南已经从灰原哀那里得到了一些关于OIBH组织的情报, 他想在阿笠把整理的资料打印出来, 仔细研究.这份资料的正文包含许多行,某些行可能包含一些脚注标记,一个脚注可能包含一行或多行,并且必须和对应的脚注标记印刷在同一页一页所允许印刷的最多行数是已知的,任何一页都不允许超过该行数(包括脚注)但是阿 …

于  CoVH系列, Vijos 继续阅读