洛谷3119 [USACO15JAN]草鉴定Grass Cownoisseur

原题链接

显然一个强连通分量里所有草场都可以走到，所以先用\(tarjan\)找强连通并缩点。

对于缩点后的\(DAG\)，先复制一张新图出来，然后对于原图中的每条边的终点向新图中该边对应的那条边的起点连一条边，表示逆向走一次，且之后不会再逆向了。

最后在该图上跑\(SPFA\)求单源最长路即可。

#include<cstdio>

using namespace std;

const int N = 1e5 + 10;

struct eg {

	int x, y;

};

eg a[N];

int fi[N], di[N], ne[N], cfi[N << 1], cdi[N << 2], cda[N << 2], cne[N << 2], dfn[N], low[N], bl[N], si[N], sta[N], q[N << 2], dis[N << 1], l, lc, ti, tp, SCC;

bool v[N << 1];

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)

{

	di[++l] = y;

	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;

}

void tarjan(int x)

{

	int i, y;

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

	sta[++tp] = x;

	v[x] = 1;

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

		if (!dfn[y = di[i]])

		{

			tarjan(y);

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

		}

		else

			if (v[y])

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

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

	{

		SCC++;

		do

		{

			y = sta[tp--];

			bl[y] = SCC;

			si[SCC]++;

			v[y] = 0;

		} while (x ^ y);

	}

}

void spfa()

{

	int head = 0, tail = 1, i, x, y;

	q[1] = bl[1];

	while (head ^ tail)

	{

		x = q[++head];

		v[x] = 0;

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

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

			{

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

				if (!v[y])

				{

					q[++tail] = y;

					v[y] = 1;

				}

			}

	}

}

int main()

{

	int i, m, x, y, n;

	n = re();

	m = re();

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

	{

		a[i].x = re();

		a[i].y = re();

		add(a[i].x, a[i].y);

	}

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

		if (!dfn[i])

			tarjan(i);

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

	{

		x = bl[a[i].x];

		y = bl[a[i].y];

		if (x ^ y)

		{

			add_c(x, y, si[x]);

			add_c(y, x + SCC, si[y]);

			add_c(x + SCC, y + SCC, si[x]);

		}

	}

	add_c(bl[1], bl[1] + SCC, si[bl[1]]);

	spfa();

	printf("%d", dis[bl[1] + SCC]);

	return 0;

}

巴特西

洛谷3119 [USACO15JAN]草鉴定Grass Cownoisseur

原题链接

最新文章

热门文章