的任意简单路径(不重复经过顶点)顶点的权值序列为,需要满足,即不单调递减,那么得分就是中不同值的个数。
中所有简单路径中最大的得分是多少

因为权值需要满足不递减的关系,所以即使能到达,但如果,那么不能走到
所以我们需要将每个点的权值从小到大排序,但是不需要排序,因为是起点。这就是运用到拓扑排序的思想,只有前面权值小的点更新了,那么我才会更新权值大的点,因为如果我直接更新权值大的点,那么会造成遗漏情况。
虽然现在确定了遍历的顺序,例如现在点,所有能够到达的点
  1. 如果,那么
  2. 如果,那么
那么可以写出下面的代码:
#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;


const int N = 2e5 + 10;

int n, m;
vector<int> adj[N];
int score[N], sum[N];
pair<int, int> pa[N];

bool cmp(pair<int, int> a, pair<int, int> b){
    return a.first < b.first;
}

signed main(){
    HelloWorld;
    
    cin >> n >> m;
    for(int i = 1; i <= n; i ++){
        cin >> score[i];
        pa[i] = {score[i], i};
    }
    sort(pa + 2, pa + 1 + n, cmp);
    for(int i = 1; i <= m; i ++){
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }    
    for(int i = 1; i <= n; i ++) sum[i] = -1e9;
    sum[1] = 1;
    for(int i = 2; i <= n; i ++){
        int v = pa[i].second;
        for(int u : adj[v]){
            if(score[u] < score[v]) sum[v] = max(sum[v], sum[u] + 1);
            else if(score[u] == score[v]) sum[v] = max(sum[v], sum[u]);
        }
    }
    cout << max(sum[n], 0LL) << endl;
    return 0;
}
但是错了,仔细分析:
思考这样一组数据:
4 3
1 2 2 3
2 4
1 3
2 3
输出的结果为0,但是显然答案为3,因为有一天简单路径134所以正确答案为3.
为什么输出0呢?因为一开始遍历的顺序为134
首先更新,那么
然后更新3,那么
最后更新4,那么
所以最终输出0
原因是并且3连通,那么我将3更新时,自然会有一条路径为,那么
所以我们还得使用并查集来维护值相同并且来连通的“块”
所以总代码:
#include<bits/stdc++.h>
using namespace std;

#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;


const int N = 2e5 + 10;

int n, m;

int p[N], sum[N], score[N];
pair<int, int> pa[N];
vector<int> adj[N];

int find(int x){
    if(x != p[x]) p[x] = find(p[x]);
    return p[x];
}

bool cmp(pair<int, int> a, pair<int, int> b){
    return a.first < b.first;
}
signed main(){
    HelloWorld;
    
    cin >> n >> m;
    for(int i = 1; i <= n; i ++){
        cin >> score[i];
        pa[i] = {score[i], i};
        sum[i] = -1e9;
        p[i] = i;
    }
    sort(pa + 2, pa + 1 + n, cmp);
    for(int i = 1; i <= m; i ++){
        int u, v; cin >> u >> v;
        if(score[u] == score[v]){
            int fu = find(u), fv = find(v);
            p[fu] = fv;
        }
        adj[u].push_back(v);
        adj[v].push_back(u);
    }    
    sum[find(1)] = 1;
    for(int i = 2; i <= n; i ++){
        int v = pa[i].second;
        for(int u : adj[v]){
            int fu = find(u), fv = find(v);
            if(score[u] < score[v]) sum[fv] = max(sum[fv], sum[fu] + 1);
            else if(score[u] == score[v]) sum[fv] = max(sum[fv], sum[fu]);
        }
    }
    cout << max(sum[find(n)], 0LL) << endl;
    return 0;
}