L2-044 大众情人 - 多源最短路 floyd

PTA | 程序设计类实验辅助教学平台

思路：

求某两点间最短路，用floyd算法【蓝桥杯集训16】多源汇求最短路——Floyd算法（2 / 2）_Roye_ack的博客-CSDN博客

用dij数组存每个人【异性到它的最短路的这个集合】中的最大值

分性别分别求出dij数组中的最小值

遍历所有人，找出男女中的"大众情人"

#include <bits/stdc++.h>
#define pb push_back 
#define INF 0x3f3f3f3f
using namespace std;const int N=510;
int g[N][N];
int sex[N],dij[N]; //dij存的是异性对自己的最短路长度
int n;void floyd() //求i和j两点间最短路
{for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
}int main()
{cin>>n;memset(g,0x3f,sizeof(g));for(int i=1;i<=n;i++){char c;cin>>c;if(c=='F') sex[i]=0;else sex[i]=1;int k;cin>>k;while(k--){int fd,d;char cc;cin>>fd>>cc>>d;g[i][fd]=d;}}floyd();//先把每个人的异性maxdij求出来for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(sex[i]!=sex[j]) dij[i]=max(dij[i],g[j][i]); //注意存的是g[j][i]int df1=INF,dm2=INF; //df1——女性maxd中的最小值  dm2——男性maxd中的最小值for(int i=1;i<=n;i++) if(sex[i]==0) df1=min(df1,dij[i]);else dm2=min(dm2,dij[i]);vector<int> f,m;for(int i=1;i<=n;i++)if(sex[i]==0&&dij[i]==df1) f.pb(i);for(int i=1;i<=n;i++)if(sex[i]==1&&dij[i]==dm2) m.pb(i);for(int i=0;i<f.size();i++){if(i!=0) cout<<" ";cout<<f[i];}cout<<endl;for(int i=0;i<m.size();i++){if(i!=0) cout<<" ";cout<<m[i];}
}

L2-043 龙龙送外卖 - 树 + dfs + 贪心

PTA | 程序设计类实验辅助教学平台

思路：

因为送完不用返回外卖站，则能发现总路程可以减少一段回城的路径
也就是【res=总路径数×2-回程距离】，想要res最小，则回程距离要最大
所以回程距离=要送买外卖点树的最大深度
首先用dfs预处理出每个分支的深度，第i个节点的深度记录在dist[i]中
遍历m个询问，对于每次加进来的新结点x所更新的图
从这个点向上找，更新sum记录的总路径数（即结点数），找过的点打上标记
每一次询问更新回程距离，即最大深度
答案就是res = sum*2-maxd

#include <bits/stdc++.h>
using namespace std;const int N=1e5+10,M=N<<1;
int h[N],ne[M],e[M],idx;
int st[N],p[N],dist[N],ver[N]; //p存节点的父节点 dist存i的深度 ver存m个询问的节点
int n,m;void add(int a,int b)
{e[idx]=b;ne[idx]=h[a];h[a]=idx++;
}void dfs(int u,int fa)
{for(int i=h[u];~i;i=ne[i]){int j=e[i];if(j==fa) continue;dist[j]=dist[u]+1;dfs(j,u);}
}int main()
{memset(h,-1,sizeof(h));cin>>n>>m;int root;for(int i=1;i<=n;i++){int x;cin>>x;if(x==-1) root=i;else{add(i,x);add(x,i);p[i]=x;}}for(int i=1;i<=m;i++) cin>>ver[i];st[root]=1;dfs(root,-1); //预处理所有节点的深度int sum=0,maxx=0;for(int i=1;i<=m;i++){int x=ver[i];while(!st[x]){sum++;st[x]=1;x=p[x];}maxx=max(maxx,dist[ver[i]]);cout<<sum*2-maxx<<endl;}    
}

L2-042 老板的作息表 - 排序 + 字符串

PTA | 程序设计类实验辅助教学平台

思路：

先把时间表排序，容易发现规律，模拟即可

00:00:00 - 01:00:05
01:00:05 - 04:30:00
05:30:00 - 06:30:00
06:30:00 - 07:10:58
07:10:59 - 08:00:00
08:00:00 - 09:00:00
13:00:00 - 18:00:00
18:00:00 - 19:00:00

#include <bits/stdc++.h>
using namespace std;int main()
{int n;cin>>n;getchar();string s[n];for(int i=0;i<n;i++){string x;getline(cin,x);s[i]=x;}sort(s,s+n);string pre;for(int i=0;i<n;i++){string t=s[i];if(i==0){if(t.substr(0,8)!="00:00:00")cout<<"00:00:00 - "<<t.substr(0,8)<<endl;}else {if(t.substr(0,8)!=pre) cout<<pre<<" - "<<t.substr(0,8)<<endl;}pre=t.substr(11);}if(s[n-1].substr(11)!="23:59:59")cout<<s[n-1].substr(11)<<" - "<<"23:59:59";
}