差分约束裸题
但是坑！
有一个点是长为10W的链，需要逆序加边才能过（真是玄学）
还有各种坑爹数据
开longlong
——代码
#include <cstdio>
#include <cstring>
#include <iostream>
#define N 200001 int n, k, cnt;
long long ans, dis[N];
int head[N], to[N << ], val[N << ], next[N << ];
bool vis[N]; inline int read()
{
int x = , f = ;
char ch = getchar();
for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -;
for(; isdigit(ch); ch = getchar()) x = (x << ) + (x << ) + ch - '';
return x * f;
} inline void add(int x, int y, int z)
{
to[cnt] = y;
val[cnt] = z;
next[cnt] = head[x];
head[x] = cnt++;
} inline bool spfa(int u)
{
int i, v;
vis[u] = ;
for(i = head[u]; i ^ -; i = next[i])
{
v = to[i];
if(dis[v] > dis[u] + val[i])
{
dis[v] = dis[u] + val[i];
if(vis[v]) return ;
else if(!spfa(v)) return ;
}
}
vis[u] = ;
return ;
} int main()
{
int i, j, x, y, z;
n = read();
k = read();
memset(head, -, sizeof(head));
for(i = n; i >= ; i--) add(, i, -);
for(i = ; i <= k; i++)
{
z = read();
x = read();
y = read();
if(z == ) add(x, y, ), add(y, x, );
if(z == )
{
add(x, y, -);
if(x == y)
{
puts("-1");
return ;
}
}
if(z == ) add(y, x, );
if(z == )
{
add(y, x, -);
if(x == y)
{
puts("-1");
return ;
}
}
if(z == ) add(x, y, );
}
if(spfa())
{
for(i = ; i <= n; i++) ans -= dis[i];
printf("%lld\n", ans);
}
else puts("-1");
return ;
}