CF-Codeforces Round #485 (Div. 2)-D-Fair

ACM模版

描述

题解

给定 n n 个城市以及 m $m$ 条路，每个城市都生产一种商品，商品的种类 k k 不超过 100 $100$ 种，现在问，每个城市想要在买到 s s 种商品的最小代价，每个城市输出一个代价值。

这里首先我们知道城市的最大值远远大于商品类型的最大值，所以一定存在很多城市生产相同的商品，所以一开始考虑的是缩点，后来发现其实 k $k$ 个 bfs b f s 就行了，根本不用缩点。

通过 k k 个 bfs $bfs$ 求出来每个城市距离第 i i 种商品的最近距离，然后排序，取最小的 s $s$ 种商品距离求和，输出即可。

代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

typedef pair<int, int> pii;

const int MAXN = 1e5 + 10;
const int MAXM = 105;

int n, m, k, s;
int vis[MAXN];
int dis[MAXN][MAXM];
vector<int> a[MAXN];
vector<int> val[MAXM];

void solve()
{
    for (int i = 1; i <= k; i++)
    {
        queue<pii> qp;
        memset(vis, 0, sizeof(vis));

        for (auto it : val[i])
        {
            vis[it] = 1;
            qp.push({
  0, it});
        }
        while (!qp.empty())
        {
            auto it = qp.front();
            qp.pop();

            dis[it.second][i] = it.first;
            for (auto it_ : a[it.second])
            {
                if (!vis[it_])
                {
                    vis[it_] = 1;
                    qp.push({it.first + 1, it_});
                }
            }
        }
    }
}

int main(int argc, const char * argv[])
{
#if DEBUG
    freopen("/Users/zyj/Desktop/input.txt", "r", stdin);
    freopen("/Users/zyj/Desktop/output.txt", "w", stdout);
#endif
    memset(dis, -1, sizeof(dis));

    cin >> n >> m >> k >> s;

    int x;
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &x);
        val[x].push_back(i);
    }
    int u, v;
    for (int i = 1; i <= m; i++)
    {
        scanf("%d%d", &u, &v);
        a[u].push_back(v);
        a[v].push_back(u);
    }

    solve();

    for (int i = 1; i <= n; i++)
    {
        vector<int> tmp;
        for (int j = 1; j <= k; j++)
        {
            if (dis[i][j] != -1)
            {
                tmp.push_back(dis[i][j]);
            }
        }
        sort(tmp.begin(), tmp.end());

        long long ans = 0;
        for (int j = 0; j < s; j++)
        {
            ans += tmp[j];
        }
        printf("%lld ", ans);
    }
    putchar(10);

    return 0;
}