从
到
的任意简单路径(不重复经过顶点)顶点的权值序列为
,需要满足
,即不单调递减,那么得分就是
中不同值的个数。
求
到
中所有简单路径中最大的得分是多少
因为权值需要满足不递减的关系,所以即使
能到达
,但如果
,那么
不能走到
所以我们需要将每个点的权值从小到大排序,但是
不需要排序,因为
是起点。这就是运用到拓扑排序的思想,只有前面权值小的点更新了,那么我才会更新权值大的点,因为如果我直接更新权值大的点,那么会造成遗漏情况。
虽然现在确定了遍历的顺序,例如现在点
,所有能够到达
的点
:
-
如果
,那么
-
如果
,那么
那么可以写出下面的代码:
#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
输出的结果为
,但是显然答案为
,因为有一天简单路径
,
,
,
所以正确答案为
.
为什么输出
呢?因为一开始遍历的顺序为
,
,
,
首先更新
,那么
然后更新
,那么
,
最后更新
,那么
所以最终输出
。
原因是
并且
和
连通,那么我将
更新时,自然会有一条路径为
,那么
所以我们还得使用并查集来维护
值相同并且来连通的“块”
所以总代码:
#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;
}



京公网安备 11010502036488号