打鼹鼠

来源和评测点

毒瘤出题人
不一定能用的luogu链接

题目

【题目大意】
鼹鼠一共在仓库中打了n个洞(用1至n编号),在这n个洞中,有些洞之间是连通的,
你可以花费一定的时间从连通的一个洞口处跑到另一个洞口处,然而有些洞之间由于货物的堆放等原因并不是连通的,
也就是你并不能直接从不连通的一个洞口处跑到另一个洞口处。(但所有的连通关系都是双向的)当你在某一时刻正好在某个洞旁时,
如果正好这个洞中有一只出现在洞口处,你就可以用手中的武器(一把大锤)消灭这支鼹鼠,当你在某一时刻停留在某个洞穴处并使用大锤时,
该洞当前出现的所有鼹鼠都将被消灭。你有t秒的时间来进行消灭鼹鼠的战斗,你也知道在这t秒内鼹鼠每次出现的时间和位置。
那么,你最多能消灭多少只鼹鼠呢?为了尽可能多的消灭鼹鼠,dd_engi为你提供了一种超级武器:
如果你在某个特定时刻在某个洞口处使用这个超级武器的话,那么这个洞以及与它直接有边相连的所有洞中此刻出现的鼹鼠都会被消灭掉。
然而,这个超级武器只能使用一次。你需要编程求出的就是:用或者不用这个超级武器,你分别能消灭多少只鼹鼠?
注意:你可以不用完你所给的时间,而且可以有一些时间你并没有来回跑动而是仅仅停在某个洞的旁边。

一些题目没有将清楚的要点:
1.注意是用超级武器杀死直接相连的,我看错然后从100=>0
2.只要你某个时刻在那里,就可以杀死所有当时在那里的鼹鼠
3.时间可能有0,坐标编号没有0
4.一开始在哪里任意
【输入格式】
第一行为三个用空格隔开的整数n、m、t,分别表示鼹鼠洞的个数和连通的边数以及你的时间t。
以下m行,每行有三个用空格隔开的整数i、j、k,表示编号i、j的两个鼹鼠洞是双向连通的,
从一个运动到另一个需要花费的时间为k。
以下每行有三个用空格隔开的整数,
第一个整数表示描述的这些鼹鼠将于第几秒末出现,
第二个整数表示描述的这些鼹鼠出现的洞的编号,
第三个整数表示这次将会出现的鼹鼠的数量。
以三个整数0表示输入的结束。
输入文件的结尾是一个回车/换行符。
【输出格式】
只需输出两个用空格隔开的整数,分别表示用和不用超级武器能消灭的最多鼹鼠数。
最后以一个回车/换行符结尾。
【输入样例】
3 2 10
1 2 1
2 3 2
1 1 1
2 2 2
3 3 3
4 1 4
2 3 3
4 2 2
6 1 4
8 2 3
10 2 2
9 1 1
7 1 5
3 2 2
8 1 8
0 0 0

【输出样例】
32 29

分析

其实是一道非常简单的DP
一开始写了个dfs,我不确定时间复杂度是否相同
注意我上面说的要点就好了
然后被第一条坑惨了,还用了并查集沾沾自喜……

代码

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
//Zory-2018
//*******************头文件*******************
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int mymax(int x,int y) {return x>y?x:y;}
//*******************实现*******************
struct pt
{
int f[1100];
int hou;
pt()
{
memset(f,0,sizeof(f));
hou=0;
}
}p[110];
struct rod
{
int y,c,g;
}e[21000];
int ln=0;
void ins(int x,int y,int c)
{
ln++;
e[ln].y=y;e[ln].c=c;
e[ln].g=p[x].hou;p[x].hou=ln;
}
//*******************主函数*******************
int f[1100][110][2];
int ff[1100][110];
int main()
{
int n,m,T;scanf("%d%d%d",&n,&m,&T);
for(int i=1;i<=n;i++) ins(i,i,1);
while(m--)
{
int x,y,c;scanf("%d%d%d",&x,&y,&c);
ins(x,y,c);ins(y,x,c);
join(x,y);
}
int a,b,c;
while(scanf("%d%d%d",&a,&b,&c)!=EOF)
{
if(a==0 and b==0 and c==0) break;
p[b].f[a]+=c;
fal[fa[b]][a]+=c;
}
int mx1=0,mx2=0;
memset(f,0,sizeof(f));
memset(ff,0,sizeof(ff));
for(int t=1;t<=T;t++)
{
for(int x=1;x<=n;x++)
{
for(int k=p[x].hou;k>0;k=e[k].g) ff[t][x]+=p[e[k].y].f[t];//包括自己
for(int k=p[x].hou;k>0;k=e[k].g)//包括自己
{
int y=e[k].y,c=e[k].c;
if(t-c<0) continue;
f[t][x][0]=mymax(f[t][x][0],f[t-c][y][0]+p[x].f[t]);
f[t][x][1]=mymax(f[t][x][1],f[t-c][y][1]+p[x].f[t]);
//f[t][x][1]=mymax(f[t][x][1],f[t-c][y][0]+ff[t][x]);
f[t][x][1]=mymax(f[t][x][1],f[t-c][y][0]+fal[fa[x]][t]);
}
mx1=mymax(mx1,f[t][x][1]),mx2=mymax(mx2,f[t][x][0]);
}
}
printf("%d %d\n",mx1,mx2);
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.cf/2018-02/打鼹鼠.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%