医院设置
题目链接: https://www.luogu.com.cn/problem/P1364
思路1: bfs+邻接矩阵
本来是想手写链表的,不过还是太麻烦了,专门去学了邻接矩阵。
总之用邻接矩阵存图,然后以分别每个顶点为根bfs遍历所有节点,由于n小于等于100.所以跑得过。
邻接矩阵学习地址:https://blog.csdn.net/jnu_simba/article/details/8866705
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
int t,vis[105],grid[105][105],arr[105],len[105];
int bfs(int index)
{
int sum=0;
memset(vis,0,sizeof(vis));
memset(len,0,sizeof(len));
queue<int> que;
que.push(index);
vis[index]=1;
while(!que.empty())
{
index=que.front();
for(int i=1;i<=t;++i)
{
if(!vis[i]&&grid[index][i]==1)
{
que.push(i);
len[i]=len[index]+1;
sum+=len[i]*arr[i];
vis[i]=1;
}
}
que.pop();
}
return sum;
}
int main()
{
cin>>t;
int u,v;
for(int i=1;i<=t;++i)
{
cin>>arr[i]>>u>>v;
if(u) {grid[i][u]=1;grid[u][i]=1;}
if(v) {grid[i][v]=1;grid[v][i]=1;}
}
int dis=1e9;
for(int i=1;i<=t;++i)
dis=min( dis, bfs(i) );
cout<<dis;
}
思路2: floyd+邻接矩阵
代码:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
int t,grid[105][105],arr[105];
int main()
{
cin>>t;
int u,v;
for(int i=1;i<=t;++i)
for(int j=1;j<=t;++j)
grid[i][j]=1e9;
for(int i=1;i<=t;++i)
{
grid[i][i]=0;
cin>>arr[i]>>u>>v;
if(u) {grid[i][u]=1;grid[u][i]=1;}
if(v) {grid[i][v]=1;grid[v][i]=1;}
}
for(int k=1;k<=t;++k)
for(int i=1;i<=t;++i)
if(i!=k)
for(int j=1;j<=t;++j)
if(j!=i&&j!=k&&grid[i][k]+grid[k][j]<grid[i][j])
grid[i][j]=grid[i][k]+grid[k][j];
int ans=1e9,sum=0;
for(int i=1;i<=t;++i)
{
sum=0;
for(int j=1;j<=t;++j)
sum+=grid[j][i]*arr[j];
ans=min(ans,sum);
}
cout<<ans;
return 0;
}
总结
学会了邻接矩阵和floyd算法,不过后者这么暴力以后应该不太用得上。其实这题我觉得是几道题里花得时间最久的,因为开始用手写链表指针一通乱指结果乱了。后来学会了邻接链表算是一大收获。不过做为bfs我觉得这题并不算难,也就是记忆化搜索巴拉巴拉地。