题解：P10935 银河
Fire__Fly
·
·
题解
原题传送门
思路
首先我们可以明显看出这是一道差分约束的题，因为亮度均为整数，所以 a>b，可以等价于 a≥b+1，所以原题中的条件可以转化为：
$T=2$ 时 $B≥A+1$。
$T=3$ 时 $A≥B$。
$T=4$ 时 $A≥B+1$。
$T=5$ 时 $B≥A$。
根据差分约束，我们可以得出当 $T=1$ 时，建一条从 $A$ 到 $B$ 边权为 $0$ 和一条从 $B$ 到 $A$ 边权为 $0$ 边；当 $T=2$ 时，建一条从 $A$ 到 $B$ 边权为 $1$ 的边；当 $T=3$ 时，建一条从 $B$ 到 $A$ 边权为 $0$ 的边；当 $T=4$ 时，建一条从 $B$ 到 $A$ 边权为 $1$ 的边；当 $T=5$ 时，建一条从 $A$ 到 $B$ 边权为 $0$ 的边。
当我们建完所有边后，我们会发现如果一个环上出现了一个边权为 $1$ 的边，那么这个不等式组就不可能成立，直接输出 $-1$ 即可。现在问题是如何找到这个环，有两种思路，一种是用spfa跑最长路判断正环，还有一种是利用tarjan缩点后看这个点的权值是否大于 $0$，但是关于spfa，~~它已经死了~~，所以我用的是第二种，缩完点后看有无两个点在同一个强连通分量里且边权为 $1$。最后按拓扑进行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");
}
```