题解：2024牛客暑期多校第5场——H [入]

英文题干

There is an undirected graph where each vertex has a unique weight .

Initially, a chess piece is placed on a vertex. In each move, the piece moves to the adjacent vertex with the smallest weight. If all adjacent vertices have weights greater than the current vertex, the movement stops immediately.

You can freely assign weights to the vertices (ensuring they are all unique) and choose the initial position of the chess piece. Your goal is to maximize the number of vertices visited by the chess piece.

Input:

The first line contains two positive integers .

The next lines each contain two positive integers , indicating an edge in the graph.

Output:

Output a single integer, which is the maximum number of vertices visited by the chess piece.

中文题干

有一个无向图，其中每个顶点都有唯一权重 。

最初，一个棋子被放置在一个顶点上。在每一步中，棋子移动到权重最小的相邻顶点。如果所有相邻顶点的权重大于当前顶点，则移动立即停止。

你可以自由分配顶点的权重 （确保它们都是唯一的），并选择棋子的初始位置。你的目标是最大化棋子访问的顶点数量。

思路

AC代码

时间复杂度：O()

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int infmin = 0xc0c0c0c0;
const int infmax = 0x3f3f3f3f;
const int maxn = 45;

vector<int> mp[maxn];
int vis[maxn]; // 可能被多次标记，开int
int ans = 0;

void dfs(int cur, int le) {  // 当前节点和当前总边数
    ans = max(ans, le);
    for (auto nxt : mp[cur]) {
        if (!vis[nxt]) {
            for (auto v : mp[cur]) {
                vis[v]++;
            }
            dfs(nxt, le + 1);
            for (auto v : mp[cur]) {
                vis[v]--;
            }
        }
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, m;
    cin >> n >> m;
    int n1, n2;
    for (int i = 1; i <= m; i++) {
        cin >> n1 >> n2;
        mp[n1].push_back(n2);
        mp[n2].push_back(n1);
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            vis[j] = 0;
        }
        vis[i] = 1;
        dfs(i, 0);
    }

    cout << ans + 1;
    return 0;
}
// Inspired by 学习中ing