赛肯德 | 2017NEERC某题

我们枚举每一条边的流量x，将它作为底流（也就是比它大的的流量变成差值，比它小的流量为0），然后我们设x就是路径上第K大的那个边的流量。然后跑最短路，加上dis[n]就是当前的答案。然后取min即可。

算法时间复杂度\(O(n^2logn)\)

为什么这样子就是最小的呢？？？？？我也很懵逼啊

因为你考虑ans_x是第K大的流量，设当前处理的为x。

如果按照上述规定来跑最短路，显然上述所求最短路加上K*ans_x就是答案，而且这个最短路径是一定确定的。下面我们就要求ans_x——如果我们进行遍历然后取min的话，如果保证x!=ans_x的时候不优呢？

如果x比ans_x小，那么“还有流量”的边一定大于等于K。这样的话最后统计答案最短路会长，x变小——但是变化幅度没有前面的大，所以不优。

如果x比ans_x大，那么“还有流量”的边一定小于等于K。这样的话最后统计答案最短路会短，x变大——但是变化幅度比前面的大，所以不优。

代码如下：

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

#include<queue>

#define MAXN 5010

using namespace std;

int n,m,t,k;

int head[MAXN],done[MAXN];

long long ans=(long long)1e15;

long long dis[MAXN];

vector<int>vec;

struct Edge{int nxt,to,dis;}edge[MAXN<<1];

struct Node

{

    int u;

    long long w;

    friend bool operator < (struct Node x,struct Node y)

        {return x.w>y.w;}

};

inline void add(int from,int to,int dis)

{

    edge[++t].nxt=head[from];

    edge[t].to=to;

    edge[t].dis=dis;

    head[from]=t;

}

inline long long dij(int x)

{

    priority_queue<Node>q;

    for(int i=0;i<=n;i++) dis[i]=(long long)1e15,done[i]=0;

    q.push((Node){1,0}); dis[1]=0;

    while(!q.empty())

    {

        int u=q.top().u; q.pop();

        if(done[u]) continue;

        done[u]=1;

        for(int i=head[u];i;i=edge[i].nxt)

        {

            int v=edge[i].to;

            long long w=max(edge[i].dis-x,0);

            //printf("v=%d w=%lld %lld\n",v,w,edge[i].dis);

            if(dis[u]+w<dis[v])

                dis[v]=dis[u]+w,q.push((Node){v,dis[v]});

        }

    }

    return dis[n];

}

int main()

{

    //freopen("skd.in","r",stdin);

    //freopen("skd.out","w",stdout);

    freopen("ce.in","r",stdin);

    scanf("%d%d%d",&n,&m,&k);

    for(int i=1;i<=m;i++)

    {

        int u,v,w;

        scanf("%d%d%d",&u,&v,&w);

        add(u,v,w),add(v,u,w);

        vec.push_back(w);

    }

    ans=dij(0);

    printf("%lld\n",ans);

    for(int i=0;i<vec.size();i++)

        ans=min(ans,1ll*vec[i]*k+dij(vec[i])),printf("%lld\n",ans);

    printf("%lld\n",ans);

    return 0;

}