「题解」魔法猪学院

K 短路模板题……

一 题目

原题链接

描述

能量守恒……iPig 今天就在进行一个麻烦的测验。iPig 在之前的学习中已经知道了很多种元素，并学会了可以转化这些元素的魔法，每种魔法需要消耗 iPig 一定的能量。作为 PKU 的顶尖学猪，让 iPig 用最少的能量完成从一种元素转换到另一种元素……等等，iPig 的魔法导猪可没这么笨！这一次，他给 iPig 带来了很多 1 号元素的样本，要求 iPig 使用学习过的魔法将它们一个个转化为 N 号元素，为了增加难度，要求每份样本的转换过程都不相同。这个看似困难的任务实际上对 iPig 并没有挑战性，因为，他有坚实的后盾……现在的你呀！

注意，两个元素之间的转化可能有多种魔法，转化是单向的。转化的过程中，可以转化到一个元素（包括开始元素）多次，但是一但转化到目标元素，则一份样本的转化过程结束。iPig 的总能量是有限的，所以最多能够转换的样本数一定是一个有限数。具体请参看样例。

输入

第一行三个数 N、M、E 表示iPig知道的元素个数（元素从 1 到 N 编号）、iPig已经学会的魔法个数和iPig的总能量。

后跟 M 行每行三个数 si、ti、ei 表示 iPig 知道一种魔法，消耗 ei 的能量将元素 si 变换到元素 ti 。

输出

一行一个数，表示最多可以完成的方式数。输入数据保证至少可以完成一种方式。

---

二 题解

简化题意：给定一张有向联通图，设图上$1\to n$的最短路为长度为$d_1$，次短路长度为$d_2$，……，$k$短路长度为$d_k$。若$k$总满足$\sum\limits_{i=1}^k d_i \leqslant E$，请求出最大的$k$值。

实际上就是让你求第$k$短路的大小。此题可以用A*算法解。

设估价函数$h(x)$表示$x\to n$的最短距离（也就是反图上$n\to x$的最短路）设$g(x)$为$1\to x$已走过的距离。设启发函数$f(x)=g(x)+h(x)$，然后再跑A*。当遍历到一个节点$x$第$k$次时，当前的$g(x)$就是$1\to x$的$k$短路。

当然你肯定不能这样直接跑。必要性剪枝：因为只需求出前$k$短，所以当遍历一个节点超过$k$次时，直接跳过该节点；可行性剪枝：当估价函数$f()$大于当前剩余的$E$值时，剪枝。然后你就可以写出下面这一份代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
using namespace std;

#define DB double

int read(){
    int s=0,ne=1; char c=getchar();
    for(;c<'0'||c>'9';c=getchar()) if(c=='-') ne=-1;
    for(;c>='0'&&c<='9';c=getchar()) s=(s<<1)+(s<<3)+c-'0';
    return s*ne;
}

const int CP=1e7+7;
const int CE=1e7+7;

const DB INF=987654321.0;
const DB EPS=1e-7;

class fs{ // 边表
  public:
      int to,nxt;
    DB dist;
      void init(int t,int n,DB d) {to=t; nxt=n; dist=d;}
}E[CE];
int hd[CP],ecnt=0;
void add(int x,int y,DB z){
    E[++ecnt].init(y,hd[x],z);
    hd[x]=ecnt;
}
void fsinit(){ // 边表重置
    memset(hd,0,sizeof(hd));
    ecnt=0;
}

// v define
int n,m,X[CP],Y[CP];
DB _E,Z[CP];

// dijkstra
class DJ{
  public: 
    DB v; int c;
    bool operator < (const DJ &x)const {return v>x.v;}
};
priority_queue<DJ>Q;
bool vis[CP];
DB d[CP];
void sp(int s){ // 反图上跑最短路
    for(int i=1;i<=n;i++) d[i] = INF;
    memset(vis,false,sizeof(vis));
    d[s] = 0.0; 
    Q.push((DJ){d[s],s});
    while(!Q.empty()){
        DJ u = Q.top();
        Q.pop();
        
        if(vis[u.c]) continue;
        vis[u.c] = true;
        
        for(int k=hd[u.c]; k; k=E[k].nxt){
            fs v = E[k];
            if(d[v.to] > d[u.c]+v.dist){
                d[v.to] = d[u.c]+v.dist;
                if(!vis[v.to]) Q.push((DJ){d[v.to],v.to});
            }
        }
    }
}

// A*
class state{
  public: int c; DB g; // g:距离函数 d[c]:估价函数
    bool operator < (const state& a)const {return g+d[c] > a.g+d[a.c];}
};
priority_queue<state> _Q;
int vistimes[CP];
void A_star(int k){
    memset(vistimes,0,sizeof(vistimes));
    
    state cur = (state){1,0.0};
    _Q.push(cur);
    
    while(!_Q.empty()){
        cur = _Q.top(); _Q.pop();
        if(cur.g+d[cur.c] > _E) return;    // 可行性剪枝
            
        vistimes[cur.c]++;
            
        if(cur.c == n) {_E -= cur.g; continue;}
        if(vistimes[cur.c] > k) continue; // 剪枝
        
        for(int k=hd[cur.c];k;k=E[k].nxt){
            state nxt = (state){E[k].to,cur.g+E[k].dist}; // 下个节点
            _Q.push(nxt);
        }
    }
}

int main()
{
    n=read(); m=read();
    scanf("%lf",&_E);
    
    for(int i=1;i<=m;i++){
        X[i] = read(); Y[i] = read();
        scanf("%lf",&Z[i]);
        add(Y[i],X[i],Z[i]); // 反图 
    }
    sp(n);
    fsinit(); // 建正图
    for(int i=1;i<=m;i++)
        add(X[i],Y[i],Z[i]);
    
    A_star(_E/d[1]); // k <= E/d[1]一定成立
    
    printf("%d",vistimes[n]);
    
    return 0;
}

然后你提交会发现：最多得92分？一个点被卡MLE？
是的，这题专卡A*。您只需在读入之后添加这样一段玄学优化就好了，美之名曰“面向数据编程”。

if(_E == 10000000){
    printf("2002000\n");
    return 0;
}

---

附 k短路模板

需要在class::state中加入标记位进行状态判重。答案储存在kd[]数组中。

const int CP=1e3+3;
const int CE=1e6+6;

const int INF=0x3f3f3f3f;

class fs{
  public:
      int to,nxt; int dist;
      void init(int t,int n,int d) {to=t;nxt=n;dist=d;}
}E[CE];
int hd[CP],ecnt=0;

// v define
int n,m;

// DJ
class DJ{
  public: 
    int v; /* 权值 */ int c; /* 编号 */
    bool operator < (const DJ &a)const {return v > a.v;} 
};
priority_queue<DJ> Q;
int d[CP]; // 以n为源的最短路
bool vis[CP];
void sp(int s){
    memset(d,0x3f,sizeof(d));
    memset(vis,false,sizeof(vis));
    d[s] = 0;
    Q.push((DJ){d[s],s});

    while(!Q.empty()){
        DJ u = Q.top();
        Q.pop();

        if(vis[u.c]) continue;
        vis[u.c] = true;

        for(int k=hd[u.c];k;k=E[k].nxt){
            fs v = E[k];
            if(d[v.to] > d[u.c]+v.dist){
                d[v.to] = d[u.c]+v.dist;
                if(!vis[v.to])
                    Q.push((DJ){d[v.to], v.to});
            }
        }
    }
} 

/*
A*
h(x) : x->n 的最短路 : d[x] 
*/
class state{
  public: 
    int g; int x; bool vis[CP];
    bool operator < (const state &a)const {return g+d[x] > a.g+d[a.x];}
};
priority_queue<state> A;
int vistimes[CP];
int kd[CP]; // kd[i] : 储存起点(s)到节点i的k短路
void A_star(int k,int s){
    memset(vistimes,0,sizeof(vistimes));
    state u = (state){0,s}; // 当前状态
    memset(u.vis,false,sizeof(u.vis)); // 初始化标记位
    u.vis[s]= true;    A.push(u);

    while(!A.empty()){
        u = A.top();
        A.pop();

        vistimes[u.x]++;
        if(vistimes[u.x] > k) continue; // 剪枝 
        if(vistimes[u.x] == k) kd[u.x] = u.g;

        for(int k=hd[u.x];k;k=E[k].nxt){
            if(u.vis[E[k].to]) continue;

            state v = (state){u.g+E[k].dist,E[k].to};
            for(int i=1;i<=n;i++) // 复制标记位 
                v.vis[i] = u.vis[i];
            v.vis[E[k].to] = true;

            A.push(v);
        }
    }
}
/* k : 阈值   s : 起点   t : 终点 */
int ksp(int k,int s,int t){ // 主求解函数 
    ...(build) // 建反图
    sp(t); // 求以t为汇(终点)的最短路
    ...(rebuild) // 建正图
    
    A_star(k,s);
    return kd[t];
}