BZOJ2330或洛谷3275 [SCOI2011]糖果

BZOJ原题链接

洛谷原题链接

很明显的差分约束，但数据范围较大，朴素\(SPFA\)判正环求解会\(T\)（理论上如此，但我看到有挺多人用朴素的还跑得挺快。。），所以需要优化。

我们所建立的有向图中所有边的权值只有\(0\)或\(1\)，而且若图中有环，那么环上所有边的权值必须为\(0\)，否则无解。

所以我们可以用\(tarjan\)找强连通分量并判断每个强连通分量有没有包含权值为\(1\)的边，有则无解。

若有解，就进行缩点，最后得到一张\(DAG\)，直接跑\(SPFA\)即可（也可按拓扑序\(DP\)，复杂度更低）。

注意有一个数据点是一条长\(10^5\)的链，若\(SPFA\)使用普通数组模拟队列会炸，须用循环队列或\(STL\)。

#include<cstdio>

#include<cstring>

using namespace std;

const int N = 1e5 + 10;

const int M = 4e5 + 10;

int fi[N], di[M], ne[M], cfi[N], cdi[M], cne[M], cda[M], da[M], dfn[N], low[N], st[N], bl[N], nw[N], dis[N], si[N], q[M], l, lc, tp, SCC, ti, k;

bool v[N], p;

inline int re()

{

	int x = 0;

	char c = getchar();

	bool p = 0;

	for (; c < '0' || c > '9'; c = getchar())

		p |= c == '-';

	for (; c >= '0' && c <= '9'; c = getchar())

		x = x * 10 + c - '0';

	return p ? -x : x;

}

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

{

	di[++l] = y;

	da[l] = z;

	ne[l] = fi[x];

	fi[x] = l;

}

inline void add_c(int x, int y, int z)

{

	cdi[++lc] = y;

	cda[lc] = z;

	cne[lc] = cfi[x];

	cfi[x] = lc;

}

inline int minn(int x, int y)

{

	return x < y ? x : y;

}

inline bool judge(int x)

{

	int i;

	for (i = fi[x]; i; i = ne[i])

		if (!(bl[di[i]] ^ SCC) && da[i])

			return true;

	return false;

}

void tarjan(int x)

{

	int i, y;

	dfn[x] = low[x] = ++ti;

	st[++tp] = x;

	v[x] = 1;

	for (i = fi[x]; i && !p; i = ne[i])

	{

		y = di[i];

		if (!dfn[y])

		{

			tarjan(y);

			low[x] = minn(low[x], low[y]);

		}

		else

			if (v[y])

				low[x] = minn(low[x], dfn[y]);

	}

	if (!(low[x] ^ dfn[x]))

	{

		SCC++;

		k = 0;

		do

		{

			y = st[tp--];

			v[y] = 0;

			bl[y] = SCC;

			nw[++k] = y;

			si[SCC]++;

		} while (x ^ y);

		for (i = 1; i <= k && !p; i++)

			if (judge(nw[i]))

				p = 1;

	}

}

int main()

{

	int i, n, m, x, y, z, head = 0, tail = 1;

	long long s = 0;

	n = re();

	m = re();

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

	{

		z = re();

		x = re() + 1;

		y = re() + 1;

		if (!(z ^ 1))

		{

			add(x, y, 0);

			add(y, x, 0);

		}

		else

			if (!(z ^ 2))

				add(x, y, 1);

			else

				if (!(z ^ 3))

					add(y, x, 0);

				else

					if (!(z ^ 4))

						add(y, x, 1);

					else

						add(x, y, 0);

	}

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

		add(1, i + 1, 1);

	for (i = 1; i <= n + 1 && !p; i++)

		if (!dfn[i])

			tarjan(i);

	if (p)

	{

		printf("-1");

		return 0;

	}

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

		for (i = fi[z]; i; i = ne[i])

		{

			y = bl[di[i]];

			x = bl[z];

			if (x ^ y)

				add_c(x, y, da[i]);

		}

	memset(dis, 250, sizeof(dis));

	dis[bl[1]] = 0;

	q[1] = bl[1];

	while (head ^ tail)

	{

		x = q[++head];

		if (!(head ^ M))

			head = 1;

		v[x] = 0;

		for (i = cfi[x]; i; i = cne[i])

		{

			y = cdi[i];

			if (dis[y] < dis[x] + cda[i])

			{

				dis[y] = dis[x] + cda[i];

				if (!v[y])

				{

					q[++tail] = y;

					if (!(tail ^ M))

						tail = 1;

					v[y] = 1;

				}

			}

		}

	}

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

		if (i ^ bl[1])

			s += 1LL * si[i] * dis[i];

	printf("%lld", s);

	return 0;

}

巴特西

BZOJ2330或洛谷3275 [SCOI2011]糖果

BZOJ原题链接

洛谷原题链接

最新文章

热门文章