tarjan求scc优化差分约束
差分约束的两种模型：求最小值和最大值 分别对应最长路和最短路。
对于最长路模型，判断是否无解的依据是图中有没有正环。考虑tarjan算法缩点后的某个scc，如果这个scc中有某条边权值大于0 ，且scc中的任意两个点都可互相到达，所以一定存在正环，即不满足差分约束的条件。
最短路模型同理。
因为同一scc内部的边权都为0，所以同一个scc中的所有点到超级源点的距离都相同，只需要对tarjan缩点后的拓扑图跑最短/长路，求出每个scc的最短/长路即可。
Acwing 368.银河
题意
银河中的恒星浩如烟海，但是我们只关注那些最亮的恒星。
我们用一个正整数来表示恒星的亮度，数值越大则恒星就越亮，恒星的亮度最暗是 1 。
现在对于 N颗我们关注的恒星，有 M 对亮度之间的相对关系已经判明。
你的任务就是求出这 N 颗恒星的亮度值总和至少有多大。
输入格式
第一行给出两个整数 N NN 和 M 。
之后 M 行，每行三个整数 T,A,B ，表示一对恒星 （A,B) 之间的亮度关系。恒星的编号从 1 开始。
如果T=1 ，说明 A和 B 亮度相等。
如果 T=2 ，说明 A 的亮度小于B 的亮度。
如果 T=3 ，说明 A 的亮度不小于 B 的亮度。
如果 T=4 ，说明 A AA 的亮度大于 B 的亮度。
如果 T=5, 说明 A 的亮度不大于 B 的亮度
思路
先根据差分约束建图，再用tarjan算法缩点求拓扑图。如果建拓扑图时，同一scc中的点之间的边权不为0，则说明有正环，无解。否则对生成的拓扑图跑最长路，最后所有scc对应的最长路长度乘以scc中点的个数即为最终答案。
代码
const int N = 1e5 + 10, M = 8 * N; int h[N],hs[N],e[M],w[M],ne[M],idx; int siz[N],id[N]; int scc,timestamp; int n, m; int dfn[N],low[N]; stack<int>stk; bool in_stk[N]; int dp[N]; void add(int h[],int a,int b,int c){ e[idx] = b,w[idx] = c,ne[idx] = h[a],h[a] = idx++; } void tarjan(int u){ dfn[u] = low[u] = ++timestamp; stk.push(u), in_stk[u] = true; for(int i = h[u];~i;i = ne[i]){ int j = e[i]; if(!dfn[j]){ tarjan(j); low[u] = min(low[u],low[j]); } else if(in_stk[j]) low[u] = min(low[u],dfn[j]); } if(dfn[u] == low[u]){ int y = 0; ++scc; do{ y = stk.top(); stk.pop(); siz[scc]++; id[y] = scc; in_stk[y] = false; }while(y != u); } } void solve() { scanf("%d%d",&n,&m); memset(h,-1,sizeof h); memset(hs,-1,sizeof hs); while(m--){ int t,u,v;scanf("%d%d%d",&t,&u,&v); if(t == 1)add(h,v,u,0),add(h,u,v,0); else if(t == 2)add(h,u,v,1); else if(t == 3)add(h,v,u,0); else if(t == 4)add(h,v,u,1); else if(t == 5)add(h,u,v,0); } for(int i = 1; i <= n;++i){ add(h,0,i,1); } tarjan(0); bool flag = true; for(int i = 0; i <= n;++i){ // 建拓扑图 for(int j = h[i];~j;j = ne[j]){ int k = e[j]; int dis = w[j]; if(id[i] != id[k]){ add(hs,id[i],id[k],dis); } else { if(dis > 0){ flag = false; break; } } } if(!flag)break; } if(!flag)puts("-1"); else { for(int i = scc; i;--i){ for(int j = hs[i];~j;j = ne[j]){ int k = e[j]; int dis = w[j]; dp[k] = max(dp[k],dp[i] + dis); } } LL res = 0; for(int i = 1; i <= scc;++i){ res += (LL)siz[i] * dp[i]; } cout << res << endl; } } signed main() { //int _; cin >> _; //while (_--) solve(); return 0; }
