ACWING 368 银河

缩点 + DAG DP + 差分约束

368. 银河 - AcWing题库

1. tarjan
2. 缩点
3. 判原图中是否有正环，因为原图上所有边都是非负的（这也是用强连通分量解差分约束的必要条件，否则若有正权边也有负权边，若环上边权总和仍为0，则并不能说明是矛盾的）， 所以如果一个强连通分量内有的边权不是 0，那么这个强连通分量中一定存在正环，所以无解
4. 若不存在正环，则在 DAG 上 DP 求最长路即可

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
typedef pair PII;
const int N = 1e5 + 10;

int n, m;
struct Edge
{
	int to;
	ll val;
};
vector G[N], E[N];

int tin[N], tim;
int scc_cnt, sz[N], id[N], low[N];
bool in_stk[N];
stack stk;

ll dist[N];
void add(int a, int b, ll c)
{
	G[a].push_back({b, c});
}

void tarjan(int u)
{
	tin[u] = low[u] = ++tim;
	stk.push(u);
	in_stk[u] = true;
	for (auto [v, w] : G[u])
	{
		if (!tin[v])
		{
			tarjan(v);
			low[u] = min(low[u], low[v]);
		}
		else if (in_stk[v])
			low[u] = min(low[u], tin[v]);
	}
	if (tin[u] == low[u])
	{
		++scc_cnt;
		int y; 
		do
		{
			y = stk.top();
			stk.pop();
			in_stk[y] = false;
			id[y] = scc_cnt;
			sz[scc_cnt]++;
		}while(y != u);
	}
}

int main()
{
	scanf("%d%d", &n, &m);
	while(m--)
	{
		int t, a, b;
		scanf("%d%d%d", &t, &a, &b);
		if (t == 1)
			add(b, a, 0), add(a, b, 0);
		else if (t == 2)
			add(a, b, 1);
		else if (t == 3)
			add(b, a, 0);
		else if (t == 4)
			add(b, a, 1);
		else
			add(a, b, 0);
	}
	for (int i = 1; i <= n; i++)
	add(0, i, 1);
	tarjan(0);
	bool flag = true;
	for (int u = 0; u <= n; u++)
	{
		for (auto [v, w] : G[u])
		{
			int a = id[u], b = id[v];
			if (a == b && w > 0)
			{
				flag = false;
				break;
			}
			else
				E[a].push_back({b, w});
		}
		if (!flag)
			break;
	}
	
	if (!flag)
	{
		cout << -1 << endl;
		return 0;
	}
	for (int u = scc_cnt; u >= 1; u--)
	{
		for (auto [v, w] : E[u])
			dist[v] = max(dist[v], dist[u] + w);
	}
	ll ans = 0;
	for (int i = 1; i <= scc_cnt; i++)
		ans += dist[i] * sz[i];
	printf("%lld\n", ans);
	return 0;
}