专栏文章

题解：P10935 银河

FFire__Fly
P10935题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mip09gyn
此快照首次捕获于
2025/12/03 04:03
3 个月前
此快照最后确认于
2025/12/03 04:03
3 个月前
查看原文

原题传送门

思路

首先我们可以明显看出这是一道差分约束的题，因为亮度均为整数，所以 a>ba>b，可以等价于 a≥b+1a≥b+1，所以原题中的条件可以转化为：
T=1T=1 时 A≥BA≥B 且 B≥AB≥A。
T=2T=2 时 B≥A+1B≥A+1。
T=3T=3 时 A≥BA≥B。
T=4T=4 时 A≥B+1A≥B+1。
T=5T=5 时 B≥AB≥A。
根据差分约束，我们可以得出当 T=1T=1 时，建一条从 AA 到 BB 边权为 00 和一条从 BB 到 AA 边权为 00 边；当 T=2T=2 时，建一条从 AA 到 BB 边权为 11 的边；当 T=3T=3 时，建一条从 BB 到 AA 边权为 00 的边；当 T=4T=4 时，建一条从 BB 到 AA 边权为 11 的边；当 T=5T=5 时，建一条从 AA 到 BB 边权为 00 的边。
当我们建完所有边后，我们会发现如果一个环上出现了一个边权为 11 的边，那么这个不等式组就不可能成立，直接输出 −1-1 即可。现在问题是如何找到这个环，有两种思路，一种是用spfa跑最长路判断正环，还有一种是利用tarjan缩点后看这个点的权值是否大于 00，但是关于spfa，它已经死了，所以我用的是第二种，缩完点后看有无两个点在同一个强连通分量里且边权为 11。最后按拓扑进行dp，答案就是把所有强连通分量的大小乘上从当前点的前驱转移到当前点的最长路径长即可。

代码

CPP
#include<bits/stdc++.h>
#define int long long
#define inf LLONG_MAX
#define mod 1000000007
using namespace std;
const int maxn = 1e6 + 100;
inline int read() {
	int x = 0 , f = 1;
	char ch = getchar();
	while (ch < '0' || ch > '9' ) {if (ch == '-') f = -1; ch = getchar();}
	while (ch >= '0' && ch <= '9') { x = x * 10 + ch - 48; ch = getchar();}
	return x * f;
}
inline void write(int x) {
	if(x < 0) x = ~(x - 1) , putchar('-');
	if(x > 9) write(x / 10);
	putchar(x % 10 + '0');
}
inline void writeh(int x) {
	write(x);
	putchar('\n');
}
inline void writek(int x) {
	write(x);
	putchar(' ');
}
int w , n , m , dp[maxn] , du[maxn] , dfn[maxn] , low[maxn] , ti , u , v , opt , vis[maxn] , stk[maxn] , top , cul[maxn] , tot , siz[maxn] , cnt;
struct node {
	int to , w;
};
vector<node> t[maxn] , t1[maxn];
inline void tarjan(int x) {
	low[x] = dfn[x] = ++ti;
	vis[x] = 1;
	stk[++top] = x;
	for(auto y:t[x]) {
		int v = y.to;
		if(!dfn[v]) {
			tarjan(v);
			low[x] = min(low[x] , low[v]);
		}else if(!cul[v]) low[x] = min(low[x] , dfn[v]);
	}
	if(dfn[x] == low[x]) {
		cul[x] = ++tot;
		siz[tot] = 1;
		while(stk[top] != x) {
			cul[stk[top--]] = tot;
			siz[tot]++;
		}
		top--;
	}
}
signed main(){
	n = read();
	m = read();
	for(int i = 1; i <= m; i++) {
		opt = read();
		u = read();
		v = read();
		if(opt == 1) {
			t[v].push_back({u , 0});
			t[u].push_back({v , 0});
		}else if(opt == 2) t[u].push_back({v , 1});
		else if(opt == 3)  t[v].push_back({u , 0});
		else if(opt == 4) t[v].push_back({u , 1});
		else t[u].push_back({v , 0});
	}
	for(int i = 1; i <= n; i++) if(!dfn[i]) tarjan(i);
	for(int i = 1; i <= n; i++) {
		for(auto y:t[i]) {
			u = i , v = y.to , w = y.w;
			if(cul[u] == cul[v] && w) {
				writeh(-1);
				return !("wjl1100 qwq");
			}
			if(cul[u] != cul[v]) t1[cul[u]].push_back({cul[v] , w}) , du[cul[v]]++;
		}
	}
	queue<int> q;
	for(int i = 1; i <= tot; i++) if(!du[i]) q.push(i) , dp[i] = 1;
	while(!q.empty()) {
		u = q.front();
		q.pop();
		for(auto y:t1[u]) {
			v = y.to , w = y.w;
			dp[v] = max(dp[v] , dp[u] + w);
			du[v]--;
			if(!du[v]) q.push(v);
		}
	}
	int ans = 0;
	for(int i = 1; i <= tot; i++) ans += siz[i] * dp[i];
	writeh(ans);
	return !("wjl1100 qwq");
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...