[spfa] Bzoj 2118 墨墨的等式

Description

　　墨墨突然对等式很感兴趣，他正在研究a1x1+a2y2+…+anxn=B存在非负整数解的条件，他要求你编写一个程序，给定N、{an}、以及B的取值范围，求出有多少B可以使等式存在非负整数解。

Input

　　输入的第一行包含3个正整数，分别表示N、BMin、BMax分别表示数列的长度、B的下界、B的上界。
　　输入的第二行包含N个整数，即数列{an}的值。

Output

　　输出一个整数，表示有多少b可以使等式存在非负整数解。

Sample Input

2 5 10
3 5

Sample Output

Hint

【数据规模】
　　对于20%的数据，N≤5，1≤BMin≤BMax≤10。
　　对于40%的数据，N≤10，1≤BMin≤BMax≤10^6。
　　对于100%的数据，N≤12，0≤ai≤4*10^5，1≤BMin≤BMax≤10^12。

题解

我们设a1表示a数组中最小的元素，dis[i]表示我通过使用若干个数，使得结果模a1=i，假设结果为x*a1+i，最小的x是多少
那么我们可以连边后求最短路来求出dis数组，最后统计答案即可
在做物品无限的背包问题时，可以把问题转换成对某个值取模后求最短路
新姿势get√

代码

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <cstring>
 4 #include <queue>
 5 #include <algorithm> 
 6 using namespace std;
 7 #define ll long long
 8 const int N=500010;
 9 int n,cnt,head[N],a[20];
10 ll l,r,ans,dis[N];
11 bool vis[N];
12 struct edge{int to,from;ll v;}e[N*12];
13 queue<int>Q;
14 void insert(int x,int y,int v) { e[++cnt].to=y,e[cnt].from=head[x],e[cnt].v=v,head[x]=cnt; }
15 void spfa()
16 {
17     Q.push(0),vis[0]=1;
18     while (!Q.empty())
19     {
20         int u=Q.front(); Q.pop();
21         for (int i=head[u];i;i=e[i].from)
22             if (dis[u]+e[i].v<dis[e[i].to]) 
23             {
24                 dis[e[i].to]=dis[u]+e[i].v;
25                 if (!vis[e[i].to]) vis[e[i].to]=1,Q.push(e[i].to);
26             }
27         vis[u]=0;
28     }
29 }
30 int main()
31 {
32     scanf("%d%lld%lld",&n,&l,&r);
33     for (int i=1;i<=n;i++) scanf("%d",&a[i]);
34     sort(a+1,a+n+1),dis[0]=0;
35     for (int i=1;i<a[1];i++) dis[i]=(ll)1e12;
36     for (int i=2;i<=n;i++) for (int j=0;j<a[1];j++) insert(j,(j+a[i]%a[1])%a[1],a[i]/a[1]+(j+a[i]%a[1]>=a[1]));
37     spfa(),ans=0;
38     for (int i=0;i<a[1];i++) ans+=max((r-i-a[1]*max((ll)0,dis[i]-1))/a[1],(ll)0)-max((l-1-i-a[1]*max((ll)0,dis[i]-1))/a[1],(ll)0);
39     printf("%lld",ans);
40 }