Luogu P5022 旅行

传送门

我记得这题我去年写了树的做法，而且好像是用链前存的图xp总之还得了些分

树的部分，贪心+dfs即可。

基环树的部分，n^2暴力枚举断哪一条边...可以到88‘

加上快读，去掉vector...总之我乱搞优化到了96'

吸氧过了...

正解似乎应该用tarjan判环，据说是nlogn

(等会去做下加强版...

代码如下

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#define MogeKo qwq
#include<algorithm>
#include<vector>
using namespace std;

const int maxn = 5005;
int n,m,x,y,k;
int a[maxn],b[maxn],tx[maxn],ty[maxn];
bool vis[maxn];
vector <int> v[maxn];

int read() {
    int x = 0,f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9') {
        if(ch == '-') f = -1;
        ch = getchar();
    }
    while('0' <= ch && ch <= '9') {
        x = x*10 + ch-'0';
        ch = getchar();
    }
    return x*f;
}

void dfs(int u,int fa,int x,int y) {
    b[++k] = u;
    if(vis[u]) return;
    vis[u] = true;
    for(int i = 0; i < v[u].size(); i++) {
        if(v[u][i] == fa) continue;
        if(u == x && v[u][i] == y) continue;
        if(u == y && v[u][i] == x) continue;
        dfs(v[u][i],u,x,y);
    }
    return;
}

void update() {
    for(int i = 1; i <= n; i++) {
        if(b[i] < a[i]) {
            for(int j = i; j <= n; j++)
                a[j] = b[j];
            break;
        }
        if(b[i] > a[i]) break;
    }
    return;
}

int main() {
    n = read(),m = read();
    for(int i = 1; i <= m; i++) {
        x = read(),y = read();
        v[x].push_back(y);
        v[y].push_back(x);
        tx[i] = x, ty[i] = y;
    }
    for(int i = 1; i <= n; i++)
        sort(v[i].begin(),v[i].end());
    a[1] = n;
    if(m == n-1)
        dfs(1,0,0,0), update();
    else
        for(int i = 1; i <= m; i++) {
            k = 0;
            memset(vis,0,sizeof(vis));
            dfs(1,0,tx[i],ty[i]);
            if(k < n) continue;
            update();
        }
    for(int i = 1; i <= n; i++)
        printf("%d ",a[i]);
    return 0;
}

View Code