[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()

{

    LL x = 0, f = 1;

    char ch = getchar();

    for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1;

    for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0';

    return x * f;

}

inline void add(int x, int y, LL z)

{

	to[cnt] = y;

	val[cnt] = z;

	next[cnt] = head[x];

	head[x] = cnt++;

}

inline void spfa()

{

	int i, u, v;

	for(i = 0; i < m; i++) dis[i] = 1e13;

	q.push(0);

	dis[0] = 0;

	while(!q.empty())

	{

		u = q.front();

		vis[u] = 0;

		q.pop();

		for(i = head[u]; ~i; i = next[i])

		{

			v = to[i];

			if(dis[v] > dis[u] + val[i])

			{

				dis[v] = dis[u] + val[i];

				if(!vis[v])

				{

					vis[v] = 1;

					q.push(v);

				}

			}

		}

	}

}

inline LL query(LL x)

{

	int i;

	LL ans = 0;

	for(i = 0; i < m; i++)

		if(dis[i] <= x)

			ans += (x - dis[i]) / m + 1;

	return ans;

}

int main()

{

	LL x, y;

	int i, j;

	n = read();

	L = read();

	R = read();

	memset(head, -1, sizeof(head));

	for(i = 1; i <= n; i++)

	{

		a[i] = read();

		if(!a[i])

		{

			i--, n--;

			continue;

		}

		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;

}

巴特西

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

最新文章

热门文章