链接：
题目大意：
对于 \(n\) 点，点有点权，从一开始，给你 \(m\) 个相对关系。求出点权和的最小值。
\(1\leq n,m\leq 10^5\)。
正文：
转化关系：
\[\begin{aligned}a_i=a_j&\rightarrow a_j\leq a_i,a_i\leq a_j\\
a_i<a_j&\rightarrow a_i< a_j\\
a_i\geq a_j&\rightarrow a_j\leq a_i\\
a_i>a_j&\rightarrow a_j< a_i\\
a_i\leq a_j&\rightarrow a_i\leq a_j\\\end{aligned}\]
然后连边，若两者之间符号是 “\(\leq\)”，边权为零，否则为一。
最后缩点跑拓扑 DP 就行了。
代码：
const int N = 1e5 + 10;
inline ll Read()
{
ll x = 0, f = 1;
char c = getchar();
while (c != '-' && (c < '0' || c > '9')) c = getchar();
if (c == '-') f = -f, c = getchar();
while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
return x * f;
}
int n, m;
int head[N], tot;
struct edge
{
int from, to, w, nxt;
}e[2 * N];
void Add(int u, int v, int w) {e[++tot] = (edge){u, v, w, head[u]}, head[u] = tot;}
int dfn[N], low[N], col[N], cnt[N], stk[N], top, num, coln;
void Tarjan(int u)
{
low[u] = dfn[u] = ++ num;
stk[++top] = u;
for (int i = head[u], v; i; i = e[i].nxt)
if(!dfn[v = e[i].to])
{
Tarjan(v);
low[u] = min(low[u], low[v]);
}else
if (!col[v])
low[u] = min(low[u], dfn[v]);
if (low[u] == dfn[u])
{
coln++;
do
{
col[stk[top]] = coln;
cnt[coln] ++;
top--;
}while(u != stk[top + 1]);
}
}
ll ind[N], dis[N], ans;
queue <int> q;
void Topo()
{
for (int i = 1; i <= coln; i++)
{
dis[i] = 1;
if(!ind[i]) q.push(i);
}
ans = 0;
while (!q.empty())
{
int u = q.front(); q.pop();
ans += dis[u] * cnt[u];
for (int v, i = head[u]; i; i = e[i].nxt)
{
--ind[v = e[i].to];
dis[v] = max(dis[v], dis[u] + e[i].w);
if (!ind[v]) q.push(v);
}
}
}
int main()
{
n = Read(), m = Read();
for (int i = 1; i <= m; i++)
{
int opt = Read(), u = Read(), v = Read();
if (opt == 1) Add(u, v, 0), Add(v, u, 0);
if (opt == 2) Add(u, v, 1);
if (opt == 3) Add(v, u, 0);
if (opt == 4) Add(v, u, 1);
if (opt == 5) Add(u, v, 0);
}
for (int i = 1; i <= n; i++)
if (!dfn[i]) Tarjan(i);
m = tot, tot = 0;
memset (head, 0, sizeof head);
for (int i = 1; i <= m; i++)
if (col[e[i].from] != col[e[i].to])
ind[col[e[i].to]]++, Add(col[e[i].from], col[e[i].to], e[i].w);
else if(e[i].w) {puts("-1"); return 0;}
Topo();
printf ("%lld", ans);
return 0;
}