JYU7月25日数据结构与图论比赛题解_c++7月25赛事

JYU7月25日数据结构与图论比赛题解

P1427 小鱼的数字游戏 点击跳转题目

简单的签到题，运用栈先进后出的知识轻松解决

#include#includeusing namespace std;int a[1000001],n;int main(){for(int i=1;;i++){cin>>a[i];if(a[i]==0){n=i;break;} } for(int i=n-1;i>=1;i--){cout<<a[i]<<\' \';}return 0;}

P1359 租用游艇 点击跳转题目

一道Dijkstra裸题
Dijkstra 算法的三个关键步骤：

• 1.找到距离起点最近的未标记顶点
• 2.标记该顶点为已处理
• 3.以该顶点为中间点更新其他顶点的最短距离

#include #include #include using namespace std;// 定义一个极大值表示两点之间不可达（无穷大）const int INF = 9999999;int main(){ int n;  // 顶点数量 int g[205][205]; // 邻接矩阵用于存储图的边权 cin >> n;  // 输入顶点数量 // 初始化邻接矩阵 for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) { if(i == j)  // 顶点到自身的距离为0 g[i][j] = 0; else  // 初始时顶点间距离设为无穷大（不可达） g[i][j] = INF; } // 输入图的边权（只输入上三角部分，因为图是无向的） // 对于无向图，g[i][j] = g[j][i]，这里只需要输入i < j的情况 for (int i = 1; i <= n-1; i++) for(int j = i+1; j <= n; j++) { cin >> g[i][j]; g[j][i] = g[i][j]; // 无向图对称，补全下三角部分 } // Dijkstra算法：求解从顶点1到其他所有顶点的最短路径 int dis[205]; // 存储从起点（顶点1）到各顶点的最短距离 int book[205]; // 标记数组：book[i]=1表示顶点i已加入最短路径集合 // 初始化标记数组，所有顶点初始均未加入集合 memset(book, 0, sizeof(book)); // 初始化距离数组：起点到各顶点的初始距离就是邻接矩阵中的直接距离 for(int i = 1; i <= n; i++) dis[i] = g[1][i]; // 起点到自身的距离为0（确保正确性） dis[1] = 0; // 标记起点已加入集合 book[1] = 1; // Dijkstra算法主循环：需要找到n-1个顶点的最短路径 for(int i = 2; i <= n; i++) { // 步骤1：找到当前未加入集合且距离起点最近的顶点u int mind = INF; // 记录最小距离 int u;  // 记录距离最近的顶点 for(int j = 1; j <= n; j++) { // 找到未标记且距离最小的顶点 if(!book[j] && dis[j] < mind) { mind = dis[j]; u = j; } } // 步骤2：将顶点u加入最短路径集合 book[u] = 1; // 步骤3：以u为中间点，更新其他未加入集合的顶点的最短距离 for(int j = 1; j <= n; j++) { // 如果经过u到j的距离更短，则更新距离 dis[j] = min(dis[j], dis[u] + g[u][j]); } } // 输出从顶点1到顶点n的最短距离 cout << dis[n]; return 0;}

B3643 图的存储 点击跳转题目

点击跳转同站的邻接矩阵和邻接表的详解
知道了邻接表和邻接矩阵的概念就很好写了

#include #include #include using namespace std;int main() { int n, m; cin >> n >> m; // 初始化邻接矩阵，n 行 n 列，初始值为 0 vector<vector<int>> adjMatrix(n, vector<int>(n, 0)); // 初始化邻接表 vector<vector<int>> adjList(n); for (int i = 0; i < m; ++i) { int u, v; cin >> u >> v; // 无向图，所以邻接矩阵中 u - 1 和 v - 1 位置都要置 1（顶点编号从 1 开始，数组索引从 0 开始） adjMatrix[u - 1][v - 1] = 1; adjMatrix[v - 1][u - 1] = 1; // 邻接表中添加相邻顶点 adjList[u - 1].push_back(v); adjList[v - 1].push_back(u); } // 输出邻接矩阵 for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { cout << adjMatrix[i][j] << \" \"; } cout << endl; } // 输出邻接表，先排序再输出 for (int i = 0; i < n; ++i) { // 对每个顶点的邻接顶点进行排序 sort(adjList[i].begin(), adjList[i].end()); // 输出度数 cout << adjList[i].size() << \" \"; for (int v : adjList[i]) { cout << v << \" \"; } cout << endl; } return 0;}

B3647 【模板】Floyd 点击跳转题目

演都不演了出模板题了 (bushi)

没什么好说的没有弯弯绕绕

1.初始化邻接矩阵：

• 用 dist 数组存储图的邻接矩阵，dist[i][j] 表示顶点 i 到顶点 j 的最短距离。
• 初始时，顶点到自身距离设为0，不同顶点间距离设为 INT_MAX（代表无穷大，即不可达）。

2.构建初始距离矩阵：

• 循环读取输入的边信息 u, v, w，由于是无向图，双向设置 dist[u][v] 和 dist[v][u] 为 w
  。若有重边，取权值较小的边更新（比较当前存储的距离和新输入的 w，保留较小值 ）。

3.Floyd 算法核心：

• 通过三重循环，枚举中间顶点 k，以及起点 i 和终点 j 。
• 若经过中间顶点 k 能让 i 到 j 的路径更短（即 dist[i][j] > dist[i][k] + dist[k][j]
  ，同时要保证 dist[i][k] 和 dist[k][j] 不是无穷大，避免溢出 ），就更新 dist[i][j] 。

4.结果输出:

• 按行输出每个顶点到其他顶点的最短距离，形成 n 行 n 列的矩阵。

#include // 用于 INT_MAX，代表无穷大#include  using namespace std;int main() { int n, m; // 输入顶点数和边数 cin >> n >> m; // 初始化邻接矩阵，n + 1 是为了让顶点编号从 1 开始，方便处理 int dist[n + 1][n + 1]; // 初始化距离矩阵，先将所有距离设为无穷大 for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { // 顶点到自身距离为 0 if (i == j) dist[i][j] = 0; else dist[i][j] = INT_MAX; } } // 输入边的信息，构建初始距离矩阵 for (int i = 0; i < m; i++) { int u, v, w; cin >> u >> v >> w; // 无向图，双向赋值，取较小值（处理重边情况） if (w < dist[u][v]) { dist[u][v] = w; dist[v][u] = w; } } // Floyd 算法核心，三重循环更新最短路径 for (int k = 1; k <= n; k++) { for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { // 若经过 k 顶点能使 i 到 j 路径更短，更新距离 if (dist[i][k] != INT_MAX && dist[k][j] != INT_MAX  && dist[i][j] > dist[i][k] + dist[k][j]) {  dist[i][j] = dist[i][k] + dist[k][j]; } } } } // 输出所有点对的最短路径结果 for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { // 输出距离，若为 INT_MAX 说明不可达（本题数据保证有解，实际可根据需求处理） cout << dist[i][j] << \" \"; } cout << endl; } return 0;}

P2097 资料分发 1 点击跳转题目

无向图求联通块的个数，遍历每个没被访问过的点，dfs能被这个点到达的点（设为被访问）
最后dfs的次数就是答案。

#includeusing namespace std;vector <int> p[100100];//p[n]存储点n所连接的点int n,m,f,s,ans,pd[100100];//ans是连通块的个数，pd数组判断这个点有没有被访问过void dfs(int x){for(int y=0;y<p[x].size();y++)//遍历所有与x相邻的边 if(pd[p[x][y]]==0)//如果这个点没有被访问过 pd[p[x][y]]=1,dfs(p[x][y]);//标记一下，访问这一个点 }int main(){cin>>n>>m;for(int x=1;x<=m;x++)cin>>f>>s,p[f].push_back(s),p[s].push_back(f);//存边 for(int x=1;x<=n;x++)if(pd[x]==0)ans++,pd[x]=1,dfs(x);//连通块的个数+1，标记并访问cout<<ans;//输出return 0;}

其实用并查集也可以。

p1506 拯救oibh总部 点击跳转题目

一道dfs+染色题
我们需要找到的是被*围住的所有区域，从（0,0）上下左右搜索染色，遇到障碍或者越界就回溯
最后会发现未被染色且非*的点就是被障碍保护的地区，最后遍历全地图寻找此类点数目即可。

#include#includeusing namespace std; char ch; int x,y,ans,map[550][550],dx[5]={0,1,-1,0,0},dy[5]={0,0,0,1,-1};//dx,dy是上下左右四个方向（把0空了过去） void dfs(int m,int n) { if(m<0||n<0||m>x+1||n>y+1||map[m][n]) //如果越界或有障碍就回溯  return; map[m][n]=2; for(int i=1;i<=4;i++) //上下左右搜索  dfs(m+dx[i],n+dy[i]);} int main(){ scanf(\"%d%d\",&x,&y); for(int i=1;i<=x;i++) //习惯处理成数字地图  for(int j=1;j<=y;j++) { cin>>ch;  if(ch==\'0\')  map[i][j]=0; else map[i][j]=1; } dfs(0,0); //洪水开始泛滥  for(int i=1;i<=x;i++) //寻找没有被洪水袭击的点即未被染色的点  for(int j=1;j<=y;j++) if(!map[i][j]) ans++; printf(\"%d\",ans); return 0; }

P1547 [USACO05MAR] Out of Hay S 点击跳转题目

一道prim算法的模板题
得到最小生成树后在所有所选边中寻找最大值。
prim算法基本思路:

• 1.任选图中的一个顶点加入到最小生成树集合中。
• 2.从已加入最小生成树集合的顶点出发，找到一条连接集合内顶点和集合外顶点且权重最小的边，将这条边和边所连接的集合外顶点加入到最小生成树集合中。
• 3.重复步骤 2，直到图中所有顶点都被加入到最小生成树集合中。

#include#include#includeusing namespace std;int dis[5000+10][5000+10],minn[6000];//dis用来存距离，minn求答案值bool vis[6000];//记录访问情况long long sum;//用来累加int main(){int n,m;scanf(\"%d%d\",&n,&m); memset(dis,0x3f3f3f3f,sizeof(dis));//初始化 for(int i=1;i<=m;i++){ int x,y,z; scanf(\"%d%d%d\",&x,&y,&z); dis[x][y]=min(dis[x][y],z);//双向图存图（邻键表） dis[y][x]=min(dis[y][x],z); } memset(vis,false,sizeof(vis));//继续初始化 memset(minn,0x3f3f3f3f,sizeof(minn)); minn[1]=0; for(int i=1;i<=n;i++){//Prim模板开始 int k=0; for(int j=1;j<=n;j++) if(!vis[j]&&minn[j]<minn[k])//找点 k=j; vis[k]=true;//标记已访问 for(int j=1;j<=n;j++) if(!vis[j]) minn[j]=min(minn[j],dis[k][j]);//更新最小值 } for(int i=1;i<=n;i++)sum=max((long long)minn[i],sum);//找最大值 printf(\"%lld\",sum);return 0;}

P1821 [USACO07FEB] Cow Party S 点击跳转题目

求 一个单源最短路 + 一个单终点最短路 的最大值。
可以反向建图，把单终点最短路转为单源最短路，跑两次dijkstra算法。

#include using namespace std;typedef long long ll; // 做题的好习惯 const int maxn = 1005; //点数 const int maxm = 100005; //边数 int n, m, s, ans[maxn], sum;struct Edge{int nxt, to, w;}e[maxm];int head[maxn], cnt;void addEdge(int u, int v, int w) {e[++cnt].nxt = head[u];e[cnt].w = w;e[cnt].to = v;head[u] = cnt; }int dis[maxn], vis[maxn];void dijkstra(int s) {for (int i = 1; i <= n; i++) dis[i] = 0x3f3f3f3f; priority_queue< pair<int, int> > q;q.push(make_pair(0, s));dis[s] = 0;while (q.size()) {int u = q.top().second;q.pop();if (vis[u]) continue;vis[u] = 1;for (int i = head[u]; i; i = e[i].nxt) {int v = e[i].to;if (dis[v] > dis[u] + e[i].w) {dis[v] = dis[u] + e[i].w;q.push(make_pair(-dis[v], v));}}}}int main() {int u[maxm], v[maxm], w[maxm];cin >> n >> m >> s;for (int i = 1; i <= m; i++) {cin >> u[i] >> v[i] >> w[i]; //先存下数据，便于以后反向建边 addEdge(u[i], v[i], w[i]); //正向建边 }dijkstra(s);for (int i = 1; i <= n; i++) ans[i] = dis[i]; //回家的最短路径 cnt = 0;memset(dis, 0, sizeof(dis));memset(head, 0, sizeof(head));memset(vis, 0, sizeof(vis));for (int i = 1; i <= m; i++) addEdge(v[i], u[i], w[i]); //反向建边dijkstra(s);for (int i = 1; i <= n; i++) {ans[i] += dis[i]; //回家的最短路+去派对的最短路=全程的最短路 sum = max(sum, ans[i]); //求最大值 }cout << sum;//输出 return 0;}