感觉我超废
我是一个连floyd都不会写了的灵魂OI选手qwq(考场上写了半天spfa然后写炸了(微笑))
floyd的暴力:
1.先建树:用邻接矩阵存。存之前记得先初始化为INF
注意是无向图。然后注意自己到自己的情况dis值=0;
2.跑一遍floyd,求最短路;
3.枚举每个点建医院,相当于求每个点作为源点的单源最短路,然后乘people数,比较大小,输出最小的一个;
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<queue> #include<string> const int INF=100000007; using namespace std; int n,dis[110][110],sum; struct people{ int num,l,r; }p[110]; int main(){ memset(dis,INF,sizeof(dis)); scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d%d%d",&p[i].num,&p[i].l,&p[i].r); if(p[i].l) dis[i][p[i].l]=1,dis[p[i].l][i]=1; if(p[i].r) dis[i][p[i].r]=1,dis[p[i].r][i]=1; dis[i][i]=0; } for(int k=1;k<=n;k++){//floyd for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++) if(dis[i][j]>dis[i][k]+dis[k][j]) dis[i][j]=dis[i][k]+dis[k][j]; } } int minn=INF; for(int i=1;i<=n;i++){//求单源最短路+乘起来; sum=0; for(int j=1;j<=n;j++) sum+=dis[i][j]*p[j].num; if(sum<minn) minn=sum; } cout<<minn<<endl; return 0; }
又是WZ的非暴力解法:
#include <iostream> #include <queue> #include <cstring> #include <limits.h> using namespace std; int n; int lch[101], rch[101], fa[101], sum[101]; int dis[101][101]; bool vis[101]; int root; int main() { cin >> n; for (int i = 1; i <= n; i++) { cin >> sum[i] >> lch[i] >> rch[i]; fa[lch[i]] = fa[rch[i]] = i; } for (int i = 1; i <= n; i++)//好像也没用 { root = i; } for (int i = 1; i <= n; i++) { queue<int> q; q.push(i); memset(vis, 0, sizeof(vis)); vis[i] = 1; dis[i][i] = 0; while (!q.empty()) { int node = q.front(); q.pop(); if (lch[node] && !vis[lch[node]])//保证左儿子右儿子以及父亲都被算到 //(这里的父亲是名义上的父亲,对于选择不同结点做根,父亲与儿子的分布是不同的 { q.push(lch[node]); vis[lch[node]] = 1; dis[i][lch[node]] = dis[i][node] + 1; } if (rch[node] && !vis[rch[node]]) { q.push(rch[node]); vis[rch[node]] = 1; dis[i][rch[node]] = dis[i][node] + 1; } if (fa[node] && !vis[fa[node]]) { q.push(fa[node]); vis[fa[node]] = 1; dis[i][fa[node]] = dis[i][node] + 1; } } } int ans, ansv = INT_MAX; for (int i = 1; i <= n; i++) { int nowans = 0; for (int j = 1; j <= n; j++) { nowans += dis[i][j] * sum[j]; } if (nowans < ansv) { ansv = nowans; ans = i;//好像没有用 } } cout << ansv << endl; }