P9659 sol

· · 题解

题意

给出优先队列优化 SPFA 的代码，要求给出一组数据使得出队次数超过 10^5 次，且限制 n \leq 100,m \leq 1000。

分析

这个所谓“优化”的 SPFA 可以被卡到指数级。

考虑构造一条边权全为 0 的链，将 SPFA 骗到链底；

然后在其回溯时的节点向外连边权为 v_0 的边，再从此外部节点向链上下一个节点连边权为 v_1 的边。只要使 v_1<0,v_0>0，且 v_0 的绝对值小于 v_1 的绝对值，即可骗其回到链底进行松弛。

多套几个这样的结构，可以发现松弛次数呈指数级增长。

可以发现在此情况下该 SPFA 的时间复杂度为 O(2^n)，足以通过此题。

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n=100,m=1000;

signed main(){
//  freopen("ans.in","w",stdout);
    cout<<n<<" "<<m<<"\n";
    vector<vector<pair<int,int>>>edge(n);
    for(int i=0;i<n/2;i++)edge[i].push_back(make_pair(i+1,0));
    int base=(1<<19);
    for(int i=n/2+1;i<n;i++){
        edge[i-n/2-1].push_back(make_pair(i,base>>1));
        edge[i].push_back(make_pair(i-n/2,-base));
        base>>=1;
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<edge[i].size();++j)printf("%d %d %d\n",i+1,edge[i][j].first+1,edge[i][j].second+1);
    }
    return 0;
}