[难]令人惊艳的最短路问题
BZOJ2118 墨墨的等式
题目
墨墨突然对等式很感兴趣，他正在研究存在非负整数解的条件，他要求你编写一个程序，给定、、以及的取值范围，求出有多少可以使等式存在非负整数解。
输入
输入的第一行包含3个正整数，分别表示、、分别表示数列的长度、的下界、的上界。输入的第二行包含N个整数，即数列的值。
输出
输出一个整数，表示有多少可以使等式存在非负整数解。
样例
input：
2 5 10
3 5
output：
5
Hint
形如
，
方程的解一共有：
五个解
题解
看题解之前大家可以先停下来想一下这道题是一个什么模型，但从模型上来讲的话，这道题的内容属于本科课内知识。
当我们拿到这个式子的时候我们对这个式子可以有什么不同意义上的解释，例如两个多项式的积，如果往这方面想的话显然会涉及到 、等多项式全家桶的一些东西，但本题的式子并不是一个多项式，而是一个方程，右边的值是给你的而不是我们要求的，而且卷积的式子往往更加复杂，再加上的范围太过于奇怪，所以我们可以暂时考虑抛开它的代数意义。
再来转化一下模型，对于这种经典的线性带系数方程，我们可以很显然的将其转化成一个多重背包问题，就对于一个容量找到多少中方案，使得背包刚好被填满。但同样的，题目的数据范围也不太像一个背包。
首先我们关注到、的范围 显然我们不能依靠枚举去解决这个东西，而考虑到我们是在计算合法的的个数，这个区间性质是满足可加减的，我们可以很自然的想到运用前缀和的思想即可。那么我们现在就考虑对与一个怎么计算，的所有满足条件的的个数。
先任选一个，由其表示的取值，由下图蓝色圈所示所示：
我们假设2是的一个合法值，即：
也就是存在一组，使得
那么必然也是的合法值
因为由：
可以得到
这样我们只需要检查这个某个合不合法再利用乘除法进行快速统计即可。
但存在一个问题合法是因为合法，但依靠给我们，，不能完全凑出一个2出来，但能凑出。所以这时候对答案的贡献就应该为
所以我们需要有一个数组来记录一下对于每个余数，用，，能凑出来的最小的满足为多少。
接下来就是非常神奇的事情了：
我们以余数，建立点集，用来表示余数为的的值，到达一个新的点时可以向周围连接条边来计算新的余数。拿样例举例:
，；
选，则点集为，，
可以看出对于到达每个余数这个点的最小代价就是从0为起点的我们的最短路，只是所有的个点都必须作为一条边引出来，模型建立好后直接跑一个即可。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,int> pii;
#define mp make_pair
const int maxn = 4e5+5;
const int MOD = 1e9+7;
#define mod(x) x % MOD
#define INF 1e15
ll dis[maxn];
vector<pii> G[maxn];
int n;
ll a[maxn];
ll Min;
void dijkstra(int s) {
fill(dis, dis + Min, INF);
priority_queue<pii, vector<pii>, greater<pii> > pq;
dis[s] = 0;
pq.push(mp(0, s));
while(pq.size()){
pii tmp = pq.top();
pq.pop();
int u = tmp.second;
if(dis[u] < tmp.first) continue;
for(int i = 0;i < G[u].size();i++){
pii tmp = G[u][i];
int v = tmp.second;
if(dis[v] > dis[u] + tmp.first){
dis[v] = dis[u] + tmp.first;
pq.push(mp(dis[v], v));
}
}
}
}
ll Calc(ll b) {
ll ans = 0;
for(int i = 0;i < Min;i++) {
if(dis[i] > b) continue;
ans += (b - dis[i]) / Min + 1;
}
return ans;
}
int main(){
ll B_Min, B_Max;
Min = INF;
scanf("%d %lld %lld", &n, &B_Min, &B_Max);
for(int i = 1;i <= n;i++) {
scanf("%lld", a + i);
if(a[i] != 0) Min = min(Min, a[i]);
}
for(int i = 0;i < Min;i++) {
for(int j = 1;j <= n;j++) {
int to = (i + a[j]) % Min;
G[i].push_back({a[j], to});
}
}
dijkstra(0);
printf("%lld\n", Calc(B_Max) - Calc(B_Min - 1));
return 0;
}
一道自认为比较优美的最短路问题，当时做的时候感觉非常惊艳，但代码写起来却非常的简单易懂。图论的强大，在于在每种问题的背后都能看见它的影子。希望这道题能给大家带来思想上的启发。