题解：CF2057E2 Another Exercise on Graphs (hard version)

· · 题解

E1

先将所有边按照边权排序，考虑在询问时二分答案。

设现在二分到了第 x 条边，那么我们将边权 \le w_{x} 的边的边权改为 0，>w_x 的改为 1，那么我们只需要判断此时 a 到 b 的最短路是否 <k 即可。

那么考虑预处理出 f_{i,j,k} 表示若边权 \le w_i 的边权改为 0，其余边的边权是 1，j 到 k 的最短路，我们不难发现由 f_{i-1} 到 f_i 的变化就是将一条边的边权由 1 改为 0，那么直接 \mathcal O(n^2) 更新即可。f_0 可以使用 floyd 求。时间复杂度 \mathcal O(n^2m)。

E2

因为这个图的边权只有 0/1，所以我们考虑将边权为 0 的边的两个端点缩在一起，只有在这些新点之间的边才是有用的，显然如果将一条两个端点已经是属于同一个新点的边的边权由 1 改为 0，这个操作显然是不会改变答案的，所以只有将两个新点合并的操作才是有用的，我们不难发现这种操作只有 n-1 个，所以时间复杂度降为 \mathcal O(n^3)。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int t,n,m,q,a,b,k,f[405][405][405],fa[405],g[405][405];
struct ee{
    int u,v,w;
    friend bool operator<(const ee&a,const ee&b){
        return a.w<b.w;
    }
}e[160005],ed[405];
int find(int x){
    return(fa[x]==x)?x:fa[x]=find(fa[x]);
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--){
        cin>>n>>m>>q;
        for(int i=1;i<=n;i++)fa[i]=i;
        memset(g,0x3f,sizeof g);
        for(int i=1;i<=m;i++)cin>>e[i].u>>e[i].v>>e[i].w,g[e[i].u][e[i].v]=g[e[i].v][e[i].u]=1;
        for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
        sort(e+1,e+m+1);
        int cnt=0;
        for(int i=1;i<=n;i++)g[i][i]=0;
        for(int i=0;i<=n-1;i++)for(int j=1;j<=n;j++)for(int k=1;k<=n;k++)f[i][j][k]=g[j][k];
        for(int i=1;i<=m;i++){
            int fx=find(e[i].u),fy=find(e[i].v);
            if(fx==fy)continue;cnt++;
            ed[cnt]=e[i],fa[fx]=fy;
            for(int x=1;x<=n;x++)for(int y=1;y<=n;y++){
                f[cnt][x][y]=min({f[cnt-1][x][y],f[cnt-1][x][e[i].u]+f[cnt-1][y][e[i].v],f[cnt-1][x][e[i].v]+f[cnt-1][y][e[i].u]});
            }
        }
        while(q--){
            cin>>a>>b>>k;
            int l=1,r=cnt,ans=0;
            while(l<=r){
                int mid=l+r>>1;
                if(f[mid][a][b]<k)ans=mid,r=mid-1;
                else l=mid+1;
            }
            cout<<ed[ans].w<<" ";
        }
        cout<<"\n";
    }
}