【6.10校内test】T2 医院设置

医院设置【题目链接】

感觉我超废

---

我是一个连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=;

using namespace std;

int n,dis[][],sum;

struct people{

    int num,l,r;

}p[];

int main(){

    memset(dis,INF,sizeof(dis));

    scanf("%d",&n);

    for(int i=;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]=,dis[p[i].l][i]=;

        if(p[i].r) dis[i][p[i].r]=,dis[p[i].r][i]=;

        dis[i][i]=;

    }

    for(int k=;k<=n;k++){//floyd

        for(int i=;i<=n;i++){

            for(int j=;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=;i<=n;i++){//求单源最短路+乘起来；

        sum=;

        for(int j=;j<=n;j++)

          sum+=dis[i][j]*p[j].num;

        if(sum<minn) minn=sum;

    }

    cout<<minn<<endl;

    return ;

}

又是water_lift的非暴力解法：

首先建树，water_lift是利用了“父子”关系建成的树，定义一个队列，依次枚举以每个结点做根的情况，然后修改权值，

开二维数组dis[i][j]和bool判断数组vis[i]，分别表示从i=>j的权值大小，是否已经计算过了，然后再跑二重循环，将dis[i][j]与对应的人数相乘，比较取最小的（好像ans是water_lift用来记录哪个结点是根的

撒花☆☆☆☆

#include <iostream>

#include <queue>

#include <cstring>

#include <limits.h>

using namespace std;

int n;

int lch[], rch[], fa[], sum[];

int dis[][];

bool vis[];

int root;

int main()

{

    cin >> n;

    for (int i = ; i <= n; i++)

    {

        cin >> sum[i] >> lch[i] >> rch[i];

        fa[lch[i]] = fa[rch[i]] = i;

    }

    for (int i = ; i <= n; i++)//好像也没用

    {

        root = i;

    }

    for (int i = ; i <= n; i++)

    {

        queue<int> q;

        q.push(i);

        memset(vis, , sizeof(vis));

        vis[i] = ;

        dis[i][i] = ;

        while (!q.empty())

        {

            int node = q.front();

            q.pop();

            if (lch[node] && !vis[lch[node]])//保证左儿子右儿子以及父亲都被算到

            //（这里的父亲是名义上的父亲，对于选择不同结点做根，父亲与儿子的分布是不同的

            {

                q.push(lch[node]);

                vis[lch[node]] = ;

                dis[i][lch[node]] = dis[i][node] + ;

            }

            if (rch[node] && !vis[rch[node]])

            {

                q.push(rch[node]);

                vis[rch[node]] = ;

                dis[i][rch[node]] = dis[i][node] + ;

            }

            if (fa[node] && !vis[fa[node]])

            {

                q.push(fa[node]);

                vis[fa[node]] = ;

                dis[i][fa[node]] = dis[i][node] + ;

            }

        }

    }

    int ans, ansv = INT_MAX;

    for (int i = ; i <= n; i++)

    {

        int nowans = ;

        for (int j = ; j <= n; j++)

        {

            nowans += dis[i][j] * sum[j];

        }

        if (nowans < ansv)

        {

            ansv = nowans;

            ans = i;//好像没有用

        }

    }

    cout << ansv << endl;

}

跑去luogu上学习了一下O（n）的算法

大概是没看懂（微笑狗）

end-