[BZOJ2118] 墨墨的等式（最短路）

传送门

好神啊。。

需要用非负数个a1,a2,a3...an来凑出B

可以知道，如果一个数x能被凑出来，那么x+a1，x+a2.......x+an也都能被凑出来

那么我们只需要选择a1~an中任意一个的a，可以求出在%a下的每个数最小需要多少才能凑出来

这样我们选择一个最小的a，速度更快，令m=min(a[k]) 1 <= k <= n

然后建模，i向(i+a[j])%m连一条权值为a[j]的边

跑一边最短路就可以了

然后需要求Bmin~Bmax中的解

只需要ans(Bmax)ans(Bmin)即可

注意a[i]==0的点。。。。

#include <queue>#include <cstdio>#include <cstring>#include <iostream>#define N 6000001#define LL long long using namespace std;int n, cnt;int head[N], to[N], next[N];LL L, R, ans, dis[N], m = ~(1 << 31), a[21], val[N];bool vis[N];queue <int> q;inline LL read()inline void add(int x, int y, LL z)inline void spfa()}}}}inline LL query(LL x)int main()m = min(m, a[i]);}for(i = 0; i < m; i++)for(j = 1; j <= n; j++)add(i, (i + a[j]) % m, a[j]);spfa();printf("%lld\n", query(R)  query(L  1));return 0;}

上一篇：[luoguP2606] [ZJOI2010]排列计数（DP）

下一篇：[luoguP3159] [CQOI2012]交换棋子（最小费用最大流）