K短路-魔法猪学院（A*算法）+骑士精神（IDA*算法）

K短路-魔法猪学院

题意：给定一个能量值 $E$E，以及一些单向边权。求所拥有的能量能从 $1$1走到 $N$N多少次，并且每一次的走法不完全一样，即求最大的 $K$K使得 前 $K$K短路的和 不大于 $E$E。

思路：

1. 建边时将正反边都记录好
2. 第一遍跑 $dijstra$dijstra或 $spfa$spfa将从 $1$1到所有点最短路求出来，作为 $A^{\ast }$A∗算法的 $g_{\left(x\right)}$g(x)​函数
3. 然后反向跑 $A^{\ast }$A∗算法（即在反向边上跑 $BFS$BFS），那么如何跑呢？
4. 我们可以利用优先队列，让 $f_{\left(x\right)}$f(x)​函数最小的节点为头节点，每次将离 $1$1尽可能近的点拿出来跑它的边，跑出的所有节点继续加到优先队列中
5. 而当每次头节点为 $1$1时，就用总能量值减去这种走法的 $h_{\left(x\right)}$h(x)​（实际上此时 $f_{\left(x\right)}=h_{\left(x\right)}$f(x)​=h(x)​，毕竟 $g_{\left(1\right)}=di{s}_{\left[1\right]}$g(1)​=dis[1]​=0），并且方案数+1，直到总能量值小于0
6. 最后，若为洛谷提交，记得加上特判，因为洛谷这道题似乎更想考察可持久化左偏树。。。然而我还不会

题目描述

iPig在假期来到了传说中的魔法猪学院，开始为期两个月的魔法猪训练。经过了一周理论知识和一周基本魔法的学习之后，iPig对猪世界的世界本原有了很多的了解：众所周知，世界是由元素构成的；元素与元素之间可以互相转换；能量守恒……。

能量守恒……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 。

输出格式

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

//#pragma comment(linker, "/STACK:102400000,102400000")
#include "bits/stdc++.h"
#define pb push_back
#define ls l,m,now<<1
#define rs m+1,r,now<<1|1
#define hhh printf("hhh\n")
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
using namespace std;
typedef long long ll;
typedef pair<double,int> pr;
inline int read() {int x=0;char c=getchar();while(c<'0'||c>'9')c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x;}

const int maxn = 2e5+10;
const int mod = 1e9+7;
const double eps = 1e-9;

int head1[maxn], nxt1[maxn], to1[maxn], tot;
int head2[maxn], nxt2[maxn], to2[maxn];
double w1[maxn], w2[maxn], dis[maxn];
int N, M, ans;
double E;

void add_edge(int u, int v, double w) {
    ++tot;
    to1[tot]=v, w1[tot]=w, nxt1[tot]=head1[u], head1[u]=tot;
    to2[tot]=u, w2[tot]=w, nxt2[tot]=head2[v], head2[v]=tot;
}

void dij() {
    for(int i=1; i<=N; ++i) dis[i]=1e12;
    priority_queue<pr,vector<pr>,greater<pr> > q;
    q.push(pr(0,1)), dis[1]=0;
    while(q.size()) {
        int now=q.top().second; q.pop();
        for(int i=head1[now]; i; i=nxt1[i]) {
            int v=to1[i];
            if(dis[v]>dis[now]+w1[i]) dis[v]=dis[now]+w1[i], q.push(pr(dis[v],v));
        }
    }
}

struct P{
    int u;
    double h, f;
    bool operator < (const P &rhs) const{
        return f>rhs.f;
    }
};

void A_star() {
    if(dis[N]>1e11) return;
    priority_queue<P> q;
    q.push((P){N,0,dis[N]});
    while(q.size()) {
        int now=q.top().u;
        double h=q.top().h; q.pop();
        if(now==1) { if((E-=h)>=0) ans++; else return; }
        for(int i=head2[now]; i; i=nxt2[i])
            q.push((P){to2[i],h+w2[i],h+w2[i]+dis[to2[i]]});
    }
}

int main() {
	//ios::sync_with_stdio(false);
    N=read(), M=read(); scanf("%lf", &E);
    if(E==10000000) return printf("2002000\n"), 0;
    for(int i=0; i<M; ++i) {
        int u=read(), v=read();
        double e; scanf("%lf", &e);
        add_edge(u,v,e);
    }
    dij();
    A_star();
    printf("%d\n", ans);
}

骑士精神

题意：给定一个正方形局面，求通过移动棋子到达目标局面的最小步数（大于15步则输出-1）。

思路：

1. 将空位看做“马”，利用DFS进行跳马操作
2. 设 $h_{\left(x\right)}$h(x)​为 $x$x局面已经走过的步数, $g_{\left(x\right)}$g(x)​为当前局面到达目标局面的最小步数
3. 若 $f_{\left(x\right)}=h_{\left(x\right)}+g_{\left(x\right)}\>15$f(x)​=h(x)​+g(x)​>15，就显然不用继续搜索了；加上这样的剪枝应该就叫 $ID{A}^{\ast }$IDA∗了？反正这样特别快
4. 当然若上面这个函数大于已经求出的 $ans$ans也不用继续搜索了
5. $h_{\left(x\right)}$h(x)​的求法就不多解释了， $A^{\ast }$A∗算法已经此题的 $ID{A}^{\ast }$IDA∗算法关键都在于 $g_{\left(x\right)}$g(x)​函数的设计
6. 首先， $g_{\left(x\right)}$g(x)​函数必须不大于 实际解 $-$− $h_{\left(x\right)}$h(x)​，即要找到一个实际解与当前局面差值的下界，并小于等于它； $g_{\left(x\right)}$g(x)​被设计的越接近这个下界就越好
7. 比如本题 $g_{\left(x\right)}$g(x)​被设计为当前局面与目标局面不同位置的数目-1（-1是因为空位与其余位置的一次交换可能使两个位置变得跟目标局面一样）

//#pragma comment(linker, "/STACK:102400000,102400000")
#include "bits/stdc++.h"
#define pb push_back
#define ls l,m,now<<1
#define rs m+1,r,now<<1|1
#define hhh printf("hhh\n")
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
using namespace std;
typedef long long ll;
typedef pair<int,int> pr;
inline int read() {int x=0;char c=getchar();while(c<'0'||c>'9')c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x;}

const int maxn = 1e5+10;
const int mod = 1e9+7;
const double eps = 1e-9;

const int terminal[5][5]={
	{1,1,1,1,1},
	{0,1,1,1,1},
	{0,0,2,1,1},
	{0,0,0,0,1},
	{0,0,0,0,0}
};
const int dx[]={-2,-2,-1,-1,1,1,2,2};
const int dy[]={-1,1,-2,2,-2,2,-1,1};

int mp[5][5], ans;

void dfs(const int &px, const int &py, const int &x, const int &y, int s) {
	int g=0;
	for(int i=0; i<5; ++i)
		for(int j=0; j<5; ++j) if(mp[i][j]!=terminal[i][j]) g++;
	if(!g) { ans=min(ans,s); return; }
	if(g+s>16||g+s>ans) return;
	for(int i=0; i<8; ++i) {
		int xx=x+dx[i];
		int yy=y+dy[i];
		if(xx>=0&&xx<5&&yy>=0&&yy<5&&(xx!=px||yy!=py)) {
			swap(mp[x][y],mp[xx][yy]);
			dfs(x,y,xx,yy,s+1);
			swap(mp[x][y],mp[xx][yy]);
		}
	}
}

void solve() {
	ans=1e9;
	int x, y;
	for(int i=0; i<5; ++i) {
		for(int j=0; j<5; ++j) {
			char c; cin>>c;
			if(c=='0') mp[i][j]=0;
			else if(c=='1') mp[i][j]=1;
			else mp[i][j]=2, x=i, y=j;
		}
	}
	dfs(x,y,x,y,0);
	cout<<(ans==1e9?-1:ans)<<endl;
}

int main() {
	//ios::sync_with_stdio(false);
	int T=read();
	while(T--) solve();
}