Description
银河中的恒星浩如烟海，但是我们只关注那些最亮的恒星。我们用一个正整数来表示恒星的亮度，数值越大则恒星就越亮，恒星的亮度最暗是 1。现在对于 N 颗我们关注的恒星，有 M 对亮度之间的相对关系已经判明。你的任务就是求出这 N 颗恒星的亮度值总和至少有多大。
Input
第一行给出两个整数N和M。
之后M行，每行三个整数T,A,B，表示一对恒星(A,B)之间的亮度关系。恒星的编号从1开始。
如果T=1，说明A和B亮度相等。
如果T=2，说明A的亮度小于B的亮度。
如果T=3，说明A的亮度不小于B的亮度。
如果T=4，说明A的亮度大于B的亮度。
如果T=5，说明A的亮度不大于B的亮度。
Output
输出一个整数表示答案。
Samples
Input
5 7 1 1 2 2 3 2 4 4 1 3 4 5 5 4 5 2 3 5 4 5 1
Output
11
Hint
对于30%的数据，N≤100。
对于100%的数据，N≤100000，M≤100000。
这个题可以用Tarjan缩点来进行处理
从题意的制约关系来看，也可以当作差分 约束 来处理
当用差分约束的时候，通过题意，我们可以了解到：题目要求我们求出N颗恒星亮度的最小值，那么我们就要求出这N个点亮度之和的最长路
然后就是普通的SPFA处理，注意在跑SPFA的时候，我们要判断是否存在一个正环，如果说存在一个正环，我们要直接输出-1,因为这个时候他的亮度值会不断的加大：
举个例子（1 > 2, 2 > 3, 3 > 4,4 > 1),这个时候我们就要像用SPFA判断是否存在负环的方式来进行判断是否存在正环，在处理的过程中，我们可以记录每个点进入队列的次数，如果说进入队列的次数大于n，说明就会有正环，但是这里其实还会有一种小的优化，如果使用queue的话，会被卡tle,但是如果是用stack就能通过这个题，其实，栈优化的SPFA在不存在负环的时候，会比队列优化的SPFA更快一些
如果代码是这个样子的：（会TLE）
const int maxn = 1e6 + 7; int n, m; ll dis[maxn]; bool vis[maxn]; struct node { int v, nex; ll w; } e[maxn]; int cnt, head[maxn]; int tot[maxn]; void init() { for(int i = 0; i <= n; i++) { dis[i] = -9999999; head[i] = -1; tot[i] = 0; } } void add(int u, int v, int w) { e[cnt].v = v; e[cnt].w = w; e[cnt].nex = head[u]; head[u] = cnt++; } int flag = 1; void spfa() { queue <int> st; dis[0] = 0; st.push(0); vis[0] = 1; while(st.size()) { int u = st.front(); st.pop(); vis[u] = 0; for(int i = head[u]; ~i; i = e[i].nex) { int to = e[i].v; if(dis[to] < dis[u] + e[i].w) { dis[to] = dis[u] + e[i].w; tot[to] = tot[u] + 1; if(tot[to] > n) { flag = 0; break; } if(vis[to] == 0) { st.push(to); vis[to] = 1; } } } if(flag == 0) break; } } int main() { cin >> n >> m; init(); for(int i = 1; i <= m; i++) { int op = read, u = read, v = read; if(op == 1) add(u, v, 0), add(v, u, 0); else if(op == 2) add(u, v, 1); else if(op == 3) add(v, u, 0); else if(op == 4) add(v, u, 1); else if(op == 5) add(u, v, 0); } for(int i = 1; i <= n; i++) add(0, i, 1);///超级源点 spfa(); /* for(int i = 1; i <= n; i++) { cout << dis[i] << endl; }*/ if(flag) { ll res = 0; for(int i = 1; i <= n; i++) { res += dis[i]; } cout << res << '\n'; return 0; } puts("-1"); return 0; } /** **/
用栈维护的：（AC）
#define Clear(x,val) memset(x,val,sizeof x) int n,m; ll dis[maxn],head[maxn],cnt; bool vis[maxn]; struct node { int u,to,w,nex; } e[maxn << 1]; void init() { cnt = 0; for(int i=0; i<=n; i++) { head[i] = -1; dis[i] = -inf; } } void add(int u,int v,int w) { e[cnt].u = u; e[cnt].to = v; e[cnt].w = w; e[cnt].nex = head[u]; head[u] = cnt ++; } int instk[maxn]; int flag; void spfa(int u) { stack <int> stk; dis[u] = 0, vis[u] = 1; stk.push(u); while(stk.size()) { u = stk.top(); // u = stk.front(); stk.pop(); vis[u] = 0; // cout << "vis : " << u << endl; for(int i=head[u]; ~i; i=e[i].nex) { int to = e[i].to, w = e[i].w; if(dis[to] < dis[u] + w) { dis[to] = dis[u] + w; instk[to] = instk[u] + 1; if(instk[to] > n) { flag = 1; return ; } if(!vis[to]) { stk.push(to); vis[to] = 1; } } } } } int main() { n = read,m = read; init(); for(int i=1; i<=m; i++) { int op = read, u = read, v = read; if(op == 1) add(u,v,0),add(v,u,0); else if(op == 2) add(u,v,1); else if(op == 3) add(v,u,0); else if(op == 4) add(v,u,1); else add(u,v,0); } for(int i=1; i<=n; i++) add(0,i,1); spfa(0); ll ans = 0; if(flag) { puts("-1"); return 0; } for(int i=1; i<=n; i++) { ans += dis[i]; } cout << ans << endl; return 0; } /** 5 7 1 1 2 2 3 2 4 4 1 3 4 5 5 4 5 2 3 5 4 5 1 **/
Tarjan有向图的连通性：
可以把这个图看成是一个有向图，首先将这个图进行缩点，过程中得到每个点属于的强连通分量以及连通块的大小size，然后判断一个点所连的边中的点是不是在一个强连通分量之中，如果有两个点在同一个强连通分量之中，那就说明是-1的情况，直接输出-1即可
排除-1的情况之后，可以对缩完之后的点重新进行建图，对于新建完的图，我们获取他们的每个强连通的最小亮度，然后将每个强连通的亮度 * size相加起来就是答案
Code:
int n,m,cnt,head[maxn],h2[maxn],cnt2; int dfc,dfn[maxn],low[maxn]; struct node { int to,nex,w; } e[maxn << 1],e2[maxn << 1]; void init() { dfc = cnt2 = cnt = 0; for(int i=0; i<=n+10; i++) { head[i] = -1; h2[i] = -1; low[i] = dfn[i] = 0; } } void add(int u,int v,int w) { e[cnt].to = v; e[cnt].w = w; e[cnt].nex = head[u]; head[u] = cnt ++; } void add2(int u,int v,int w) { e2[cnt2].to = v; e2[cnt2].w = w; e2[cnt2].nex = h2[u]; h2[u] = cnt2 ++; } bool inStk[maxn]; stack<int> stk; ll pos[maxn], cntSCC; ll siz[maxn]; void Tarjan(int u) { dfn[u] = low[u] = ++ dfc; stk.push(u); inStk[u] = 1; for(int i=head[u]; ~i; i=e[i].nex) { int to = e[i].to; if(!dfn[to]) { Tarjan(to); low[u] = min(low[u],low[to]); } else if(inStk[to]) {///to in stack low[u] = min(low[u],dfn[to]); } } if(dfn[u] == low[u]) { int tp; ++ cntSCC; do { tp = stk.top(); stk.pop(); inStk[tp] = 0; siz[cntSCC] ++; pos[tp] = cntSCC; } while(tp != u); } } ll dis[maxn]; int main() { n = read,m = read; init(); for(int i=1; i<=m; i++) { int op = read,u = read,v = read; if(op == 1) add(u,v,0),add(v,u,0); else if(op == 2) add(u,v,1); else if(op == 3) add(v,u,0); else if(op == 4) add(v,u,1); else add(u,v,0); } for(int i=1; i<=n; i++) add(0,i,1); Tarjan(0); for(int i=0; i<=n; i++) { int u = i; for(int j=head[u]; ~j; j=e[j].nex) { int to = e[j].to; if(pos[u] == pos[to]) { if(e[j].w) { puts("-1"); return 0; } } else add2(pos[u],pos[to],e[j].w); } } ll ans = 0; /// use e2 not e and use h2 for(int i=cntSCC; i; i--) { int u = i; for(int j=h2[u]; ~j; j=e2[j].nex) { int to = e2[j].to; dis[to] = max(dis[to],dis[u] + e2[j].w); } } for(int i=1; i<=cntSCC; i++) { ans += dis[i] * siz[i]; } cout << ans << endl; return 0; } /** 5 7 1 1 2 2 3 2 4 4 1 3 4 5 5 4 5 2 3 5 4 5 1 **/
