L2-3 智能护理中心统计
智能护理中心系统将辖下的护理点分属若干个大区，例如华东区、华北区等；每个大区又分若干个省来进行管理；省又分市，等等。我们将所有这些有管理或护理功能的单位称为“管理结点”。现在已知每位老人由唯一的一个管理结点负责，每个管理结点属于唯一的上级管理结点管辖。你需要实现一个功能，来统计任何一个管理结点所负责照看的老人的数量。
注意这是一个动态问题，即随时可能有老人加入某个管理结点，并且老人是有可能从一个管理结点换到另一个管理结点去的。
输入格式：
输入在第一行中给出 2 个正整数：N（≤104）是老人的总数量，即老人们从 1 到 N 编号；M（≤105）是归属关系的总数。
接下来是 M 行，每行给出一对归属关系，格式为：
A B表示 A 归属于 B。A 或 B 如果是某个管理结点，则用不超过 4 个大写英文字母表示其名称；如果是某位老人，则用老人的编号表示。这里每个 A 保证只有唯一的上级归属 B，且只有这个中心系统本身是没有上级归属的。此外，输入保证没有老人自己承担管理结点的角色，即 B 一定是一个管理结点，不可能是老人的编号。但一个管理结点既可以管辖下级结点，也可以直接护理一部分老人。
随后每行给出一个指令，格式为：
指令 内容如果 指令 为 T，则表示有老人要入院或转院，内容 是某老人的编号和要去的管理结点的名称，以空格分隔；如果 指令 为 Q，则 内容 是一个管理结点的名称，意思是统计这个结点所负责照看的老人的数量；如果 指令 为 E，则表示输入结束。题目保证指令总数不会超过 100 个。
输出格式：
对每个 T 指令，将对应的老人转存到对应的管理结点名下；对每个 Q 指令，在一行中输出对应管理结点所负责照看的老人的数量。读到 E 指令就结束程序。
输入样例：
10 23
EAST CNTR
ZJ EAST
SD EAST
WEST CNTR
SX WEST
HZ ZJ
JN SD
2 JN
8 JTH
6 XAHP
4 ZDYH
5 ZDYH
ZDYH HZ
HUZ ZJ
JX ZJ
1 JX
3 JN
WZ ZJ
XAHP XIAN
XIAN SX
YL SX
JTH XIAN
7 XAHP
Q EAST
T 1 YL
Q EAST
Q SX
T 8 ZDYH
Q HZ
Q HUZ
T 10 XAHP
Q CNTR
E输出样例：
5
4
4
3
0
9
题解：老人为叶子节点，考虑到每次只有叶子节点的变化，所以只需要贪心计算叶子节点对对应的这条链的贡献即可
// #include<bits/stdc++.h> using namespace std; #define maxn 610938 #define inf 1290311 int n,m,t; struct no { int x,y,nowtime,shu; }; map<pair<int,int> ,pair<int,int>>mp; int mapp[200][200]; queue<no>Q; int dx[6]={1,-1,0,0}; int pre1[200]; int pre2[200]; int dy[6]={0,0,1,-1}; int mark[200][200]; int tx,ty; int dis[200][200][2]; void bfs() { dis[tx][ty][0]=0; dis[tx][ty][1]=0; memset(mark,0,sizeof(mark)); queue<pair<int,int> >K; K.push(make_pair(tx,ty)); while(K.size()) { pair<int ,int> p1=K.front(); K.pop(); int x=p1.first; int y=p1.second; mark[x][y]=0; for(int i=0;i<4;i++) { if(x+dx[i]>=2&&y+dy[i]>=2&&x+dx[i]<=n+1&&y+dy[i]<=m+1) { if(x+dx[i]==tx&&y+dy[i]==ty)continue; if(dis[x+dx[i]][y+dy[i]][0]>dis[x][y][0]+1+mapp[x+dx[i]][y+dy[i]]) { dis[x+dx[i]][y+dy[i]][0]=dis[x][y][0]+1+mapp[x+dx[i]][y+dy[i]]; if(!mark[x+dx[i]][y+dy[i]]) { mark[x+dx[i]][y+dy[i]]=1; K.push(make_pair(x+dx[i],y+dy[i])); } } } } } memset(mark,0,sizeof(mark)); K.push(make_pair(tx,ty)); while(K.size()) { pair<int ,int> p1=K.front(); K.pop(); int x=p1.first; int y=p1.second; mark[x][y]=0; for(int i=0;i<4;i++) { if(x+dx[i]>=2&&y+dy[i]>=2&&x+dx[i]<=n+1&&y+dy[i]<=m+1) { if(x+dx[i]==tx&&y+dy[i]==ty)continue; if(dis[x+dx[i]][y+dy[i]][1]>dis[x][y][1]+mapp[x+dx[i]][y+dy[i]]) { dis[x+dx[i]][y+dy[i]][1]=dis[x][y][1]+mapp[x+dx[i]][y+dy[i]]; mp[make_pair(x+dx[i],y+dy[i])]=make_pair(x,y); if(!mark[x+dx[i]][y+dy[i]]) { mark[x+dx[i]][y+dy[i]]=1; K.push(make_pair(x+dx[i],y+dy[i])); } } else { if(dis[x+dx[i]][y+dy[i]][1]==dis[x][y][1]+mapp[x+dx[i]][y+dy[i]]) { if(dis[x+dx[i]][y+dy[i]][0]<=dis[x][y][0]+1+mapp[x+dx[i]][y+dy[i]])continue; mp[make_pair(x+dx[i],y+dy[i])]=make_pair(x,y); if(!mark[x+dx[i]][y+dy[i]]) { mark[x+dx[i]][y+dy[i]]=1; K.push(make_pair(x+dx[i],y+dy[i])); } } } } } } } int main() { cin>>n>>m>>t; for(int i=1;i<=n+2;i++) for(int j=1;j<=m+2;j++) { { dis[i][j][0]=inf; dis[i][j][1]=inf; } cin>>mapp[i][j]; if(i==1||i==n+2||j==1||j==m+2) { if(!mapp[i][j]) continue; if(i==1&&(j==1||j==m+2))continue; if(i==n+2&&(j==1||j==m+2))continue; for(int k=0;k<4;k++) { if(i+dx[k]>=2&&j+dy[k]>=2&&i+dx[k]<=n+1&&j+dy[k]<=m+1) { Q.push(no{i+dx[k],j+dy[k],0,mapp[i][j]}); } } } if(mapp[i][j]<0) { tx=i; ty=j; } } int fla=0; bfs(); while(Q.size()) { no tmp=Q.front(); Q.pop(); int x=tmp.x; int y=tmp.y; int pret=1+mapp[x][y]; int num=tmp.shu; if(num>mapp[x][y]) { num-=mapp[x][y]; mapp[x][y]=0; } else { mapp[x][y]-=num; continue; } while(!(x==tx&&y==ty)) { pair<int,int>R; R=mp[make_pair(x,y)]; x=R.first; y=R.second; if(mapp[x][y]) { if(x==tx&&y==ty)continue; pret=pret+1+mapp[x][y]; if(num>mapp[x][y]) { num-=mapp[x][y]; mapp[x][y]=0; } else { mapp[x][y]-=num; break; } } else { if(x==tx&&y==ty)continue; pret++; } } if(x==tx&&y==ty) { int w=max(0,min(t-pret,num)); mapp[tx][ty]+=w; mapp[tx][ty]=min(mapp[tx][ty],0); if(mapp[tx][ty]==0) { fla=1; } } } for(int i=2;i<=n+1;i++) for(int j=2;j<=m+1;j++) { if(j==2) cout<<mapp[i][j]; else { cout<<" "<<mapp[i][j]; if(j==m+1&&i!=n+1) cout<<endl; } } if(fla==1) { cout<<endl; cout<<"Game Over"; } }
--------------------
L3-1 塔防游戏
有一种简单的塔防游戏是这样的：给定一张由 n 行 m 列个方格子构成的地图，玩家可以任选一个格子放置自己的大本营，还可以在任意一个格子里放置自己的防御堡垒。大本营和每个防御堡垒都有自己的防御能力值 d，表示可以抵御 d 个僵尸的攻击。每一轮游戏开始时，玩家在规定时间内将本级别可以用的防御堡垒布置在地图中，然后僵尸们就从地图边界涌入地图中，向着大本营发起攻击。每轮进攻持续一个固定的时长，结束后剩余的僵尸就原地蒸发。
每队僵尸可以向一个方格的上下左右四个方向移动。如果相邻的目标方格没有堡垒，它们就可以用 1 秒的时间移动过去，否则会被堡垒阻挡或者消灭。对每一队僵尸（从同一地点出发的所有僵尸）而言，每秒会被堡垒消灭 1 个队友，同时消耗掉该堡垒 1 个单位的防御能力。当防御能力降为 0，则该堡垒消失，剩下的僵尸则用 1 秒移动到这个方格继续行进。注意：如果有多支僵尸队都进入了同一个方格，它们并不会合并成一支队伍。
所有的僵尸队都会根据进攻开始时的地图选择被歼灭最少的到达大本营的路线，并且一直按照这个路线行进，中途不因为地图状态的改变而改变。当这样的进攻路径不唯一时，选择能最快到达大本营的路径。题目保证这样的路径所打掉的堡垒的布局是唯一的。
本题就要求你计算出一轮攻击结束时，地图上的布局情况。
输入格式：
输入首先在第一行中给出三个正整数：不超过 100 的 n 和 m，为地图的尺寸；不超过 1000 的 T，为一轮攻击持续的时长。
随后给出 n+2 行，每行给出 m+2 个数字，每行中的数字都用空格分隔，表示攻击开始前地图上的布局。其中第 1 行、第 1 列、第 n+2 行、第 m+2 列是地图边界外僵尸们出发的位置，这些位置上，0 表示没有僵尸，其他正整数表示从该位置出发的僵尸们的数量。而地图中的每个位置上，0 表示没有堡垒，其它正整数表示该位置上堡垒的防御能力值。大本营是一个特殊的建筑，我们用一个负数 −D 表示这里是大本营，其防御能力值为 D。这里的防御值和任一队僵尸的数量都不超过 100。
注意：僵尸不可在地图边界外移动，它们的第一个移动目标必须在地图中，所以四个角落里出现的僵尸可以被忽略，因为它们没有进入地图的途径。
输出格式：
输出 n 行，每行 m 个数字，对应攻击结束后地图上每个方格的状态。状态的表示与输入相同：没有堡垒的地方输出 0，有堡垒的地方输出其剩余防御值，大本营的位置上输出其剩余防御值的负值。
注意每行数字间以 1 个空格分隔，行首尾不得有多余空格。
当大本营被攻陷时，游戏即刻结束。此时应输出结束时的地图状态，并且在最后一行输出一句 Game Over。
输入样例 1：
7 5 17
0 0 0 0 13 0 0
0 0 0 0 0 0 0
0 0 0 8 0 0 0
0 0 0 0 2 1 0
0 0 0 7 5 3 0
8 0 1 4 -10 1 0
0 0 0 3 3 0 0
0 0 8 0 9 0 0
0 0 0 4 0 0 0
输出样例 1：
0 0 0 0 0
0 0 8 0 0
0 0 0 2 0
0 0 7 5 0
0 0 0 -1 0
0 0 0 2 0
0 8 0 9 0
样例说明：
地图布局如下图所示。
规模为 13 和 8 的两队僵尸都有两种选择，攻打蓝色或者紫色堡垒都是消耗最少的。在这种情况下，规模为 13 的僵尸队走蓝色比较快，需要 1+1+1+2+4+2=11 秒到达大本营边上；规模为 8 的僵尸队走紫色比较快，需要 1+2+5=8 秒到达大本营边上。
规模为 4 的僵尸队比较惨，只能选择绿色堡垒，最后被大本营边上的绿色堡垒消灭。注意到在攻击过程中，其实它们可以等到紫色堡垒被攻陷之后走紫色原始值为 4 的方格，但是因为路径是在初始状态下选定就不能改的，所以它们不能这样选择。
攻打大本营时，规模为 8 的僵尸队剩下了 3 只先到达，在第 11 秒被大本营消灭。此时大本营还剩 7 个单位的防御值，同时规模为 13 的僵尸队剩下的 8 只进入了大本营相邻的方格，开始攻击。但此时距离本轮结束只剩 6 秒，结果大本营在结束时还剩 1 个单位的防御值，玩家胜。
输入样例 2：
7 5 20
0 0 0 0 13 0 0
0 0 0 0 0 0 0
0 0 0 8 0 0 0
0 0 0 0 2 1 0
0 0 0 7 5 3 0
8 0 1 4 -10 1 0
0 0 0 3 3 0 0
0 0 8 0 9 0 0
0 0 0 4 0 0 0
输出样例 2：
0 0 0 0 0
0 0 8 0 0
0 0 0 2 0
0 0 7 5 0
0 0 0 0 0
0 0 0 2 0
0 8 0 9 0
Game Over题解:
最开始以为是简单的bfs，然后发现题目中有个很关键的点，所有的僵尸队都会根据进攻开始时的地图选择被歼灭最少的到达大本营的路线，并且一直按照这个路线行进，
中途不因为地图状态的改变而改变。当这样的进攻路径不唯一时，选择能最快到达大本营的路径。题目保证这样的路径所打掉的堡垒的布局是唯一的。
也就是说行经路线是一开始就定好的，所以不用宽搜。所以考虑spfa和dij的做法，由于这俩都是单源最短路，所以考虑反向从大本营开始跑spfa。 dis[i][0]代表破坏堡垒和移动的总消耗的最短路径，dis[i][1]代表仅破坏堡垒的总消耗的最短路径。然后我们对于每个网格点，记录是哪一个最小损失僵尸的点更新的他就行了。
最后按照这个路径进行模拟就行。
大致思路就是这样，但是天梯赛的数据真的好多坑。。。不想改了。。。
下面附上一个23分的代码
// #include<bits/stdc++.h> using namespace std; #define maxn 610938 #define inf 1290311 int n,m,t; struct no { int x,y,nowtime,shu; }; map<pair<int,int> ,pair<int,int>>mp; int mapp[200][200]; queue<no>Q; int dx[6]={1,-1,0,0}; int pre1[200]; int pre2[200]; int dy[6]={0,0,1,-1}; int mark[200][200]; int tx,ty; int dis[200][200][2]; void bfs() { dis[tx][ty][0]=0; dis[tx][ty][1]=0; memset(mark,0,sizeof(mark)); queue<pair<int,int> >K; K.push(make_pair(tx,ty)); while(K.size()) { pair<int ,int> p1=K.front(); K.pop(); int x=p1.first; int y=p1.second; mark[x][y]=0; for(int i=0;i<4;i++) { if(x+dx[i]>=2&&y+dy[i]>=2&&x+dx[i]<=n+1&&y+dy[i]<=m+1) { if(x+dx[i]==tx&&y+dy[i]==ty)continue; if(dis[x+dx[i]][y+dy[i]][0]>dis[x][y][0]+1+mapp[x+dx[i]][y+dy[i]]) { dis[x+dx[i]][y+dy[i]][0]=dis[x][y][0]+1+mapp[x+dx[i]][y+dy[i]]; if(!mark[x+dx[i]][y+dy[i]]) { mark[x+dx[i]][y+dy[i]]=1; K.push(make_pair(x+dx[i],y+dy[i])); } } } } } memset(mark,0,sizeof(mark)); K.push(make_pair(tx,ty)); while(K.size()) { pair<int ,int> p1=K.front(); K.pop(); int x=p1.first; int y=p1.second; mark[x][y]=0; for(int i=0;i<4;i++) { if(x+dx[i]>=2&&y+dy[i]>=2&&x+dx[i]<=n+1&&y+dy[i]<=m+1) { if(x+dx[i]==tx&&y+dy[i]==ty)continue; if(dis[x+dx[i]][y+dy[i]][1]>dis[x][y][1]+mapp[x+dx[i]][y+dy[i]]) { dis[x+dx[i]][y+dy[i]][1]=dis[x][y][1]+mapp[x+dx[i]][y+dy[i]]; mp[make_pair(x+dx[i],y+dy[i])]=make_pair(x,y); if(!mark[x+dx[i]][y+dy[i]]) { mark[x+dx[i]][y+dy[i]]=1; K.push(make_pair(x+dx[i],y+dy[i])); } } else { if(dis[x+dx[i]][y+dy[i]][1]==dis[x][y][1]+mapp[x+dx[i]][y+dy[i]]) { if(dis[x+dx[i]][y+dy[i]][0]<=dis[x][y][0]+1+mapp[x+dx[i]][y+dy[i]])continue; mp[make_pair(x+dx[i],y+dy[i])]=make_pair(x,y); if(!mark[x+dx[i]][y+dy[i]]) { mark[x+dx[i]][y+dy[i]]=1; K.push(make_pair(x+dx[i],y+dy[i])); } } } } } } } int main() { cin>>n>>m>>t; for(int i=1;i<=n+2;i++) for(int j=1;j<=m+2;j++) { { dis[i][j][0]=inf; dis[i][j][1]=inf; } cin>>mapp[i][j]; if(i==1||i==n+2||j==1||j==m+2) { if(!mapp[i][j]) continue; if(i==1&&(j==1||j==m+2))continue; if(i==n+2&&(j==1||j==m+2))continue; for(int k=0;k<4;k++) { if(i+dx[k]>=2&&j+dy[k]>=2&&i+dx[k]<=n+1&&j+dy[k]<=m+1) { Q.push(no{i+dx[k],j+dy[k],0,mapp[i][j]}); } } } if(mapp[i][j]<0) { tx=i; ty=j; } } int fla=0; bfs(); while(Q.size()) { no tmp=Q.front(); Q.pop(); int x=tmp.x; int y=tmp.y; int pret=1+mapp[x][y]; int num=tmp.shu; if(num>mapp[x][y]) { num-=mapp[x][y]; mapp[x][y]=0; } else { mapp[x][y]-=num; continue; } while(!(x==tx&&y==ty)) { pair<int,int>R; R=mp[make_pair(x,y)]; x=R.first; y=R.second; if(mapp[x][y]) { if(x==tx&&y==ty)continue; pret=pret+1+mapp[x][y]; if(num>mapp[x][y]) { num-=mapp[x][y]; mapp[x][y]=0; } else { mapp[x][y]-=num; break; } } else { if(x==tx&&y==ty)continue; pret++; } } if(x==tx&&y==ty) { int w=max(0,min(t-pret,num)); mapp[tx][ty]+=w; mapp[tx][ty]=min(mapp[tx][ty],0); if(mapp[tx][ty]==0) { fla=1; } } } for(int i=2;i<=n+1;i++) for(int j=2;j<=m+1;j++) { if(j==2) cout<<mapp[i][j]; else { cout<<" "<<mapp[i][j]; if(j==m+1&&i!=n+1) cout<<endl; } } if(fla==1) { cout<<endl; cout<<"Game Over"; } }