自动搬运

查看原文

来自洛谷，原作者为

	mengleo never gonna give you up

搬运于2025-08-24 22:53:21，当前版本为作者最后更新于2024-01-17 16:14:35，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

[USACO20OPEN] Cowntact Tracing B 题解

思路

既然 $N \leq 100$，$T \leq 250$，那就有一种最暴力的解法：

1. 将时间戳以 $t$ 为关键字从小到大排序。
2. 枚举零号病人 $z$（$[1, N]$），对于每个零号病人，枚举 $k$（$[1, \color{#900021}{T + 1}\color{black}]$）。
3. 对于每对 $z, k$ 顺序遍历时间戳数组，暴力模拟感染。
4. 如果感染结果与输入的字符串一致，那么可能为零号病人的奶牛数量+1，并更新 $k$ 的上下限。
5. 输出，如果 $k$ 的上限是 $T + 1$ 就输出Infinity，否则正常输出。

时间复杂度为 $\mathcal{O}(NT^2)$。

Code

#include <bits/stdc++.h>
#define int long long

using namespace std;

struct lst_t
{
    int t, x, y;
} lst[255];
int n, t, cnt, mx, mn = LLONG_MAX;
string s;

bool cmp(lst_t x, lst_t y)
{
    return x.t < y.t;
}

signed main()
{
    cin >> n >> t >> s;
    for(int i = 1; i <= t; i++)
    {
        cin >> lst[i].t >> lst[i].x >> lst[i].y;
    }
    sort(lst + 1, lst + 1 + t, cmp);
    for(int z = 1; z <= n; z++)
    {
        bool f = 0;
        for(int k = 0; k <= t + 1; k++)
        {
            bool f2 = 1;
            int cs[n + 5] = {};
            memset(cs, -1, sizeof(cs));
            cs[z] = k;
            for(int i = 1; i <= t; i++)
            {
                if(cs[lst[i].x] == -1 && cs[lst[i].y] > 0)
                {
                    cs[lst[i].y]--;
                    cs[lst[i].x] = k;
                }
                else if(cs[lst[i].y] == -1 && cs[lst[i].x] > 0)
                {
                    cs[lst[i].x]--;
                    cs[lst[i].y] = k;
                }
                else if(cs[lst[i].x] >= 0 && cs[lst[i].y] >= 0)
                {
                    cs[lst[i].x] = max(0ll, cs[lst[i].x] - 1);
                    cs[lst[i].y] = max(0ll, cs[lst[i].y] - 1);
                }
            }
            for(int i = 1; i <= n; i++)
            {
                if((s[i - 1] == '1' && cs[i] == -1) || (s[i - 1] == '0' && cs[i] != -1))
                {
                    f2 = 0;
                }
            }
            if(f2)
            {
                mx = max(mx, k);
                mn = min(mn, k);
                f = 1;
            }
        }
        cnt += f;
    }
    cout << cnt << " " << mn;
    if(mx == t + 1)
    {
        cout << " Infinity";
    }
    else
    {
        cout << " " << mx;
    }
    
    return 0;
}