【题目链接】
【算法】
当x = 1时,连边(a,b,0)和(b,a,0)
当x = 2时,连边(a,b,1)
当x = 3时,连边(b,a,0)
当x = 4时,连边(b,a,1)
当x = 5时,连边(a,b,0)
建立超级源点(Super Source),将这个点与所有点连一条权值为1的边,注意加边时要倒着加,否则会时间超限
【代码】
#include<bits/stdc++.h>
using namespace std;
#define MAXN 100010 struct Edge
{
int to;
long long w;
int nxt;
} e[MAXN<<]; int x,a,b,i,n,k,tot;
long long dis[MAXN];
int head[MAXN]; template <typename T> inline void read(T &x)
{
int f = ; x = ;
char c = getchar();
for (; !isdigit(c); c = getchar()) { if (c == '-') f = -f; }
for (; isdigit(c); c = getchar()) x = (x << ) + (x << ) + c - '';
x *= f;
}
template <typename T> inline void write(T x)
{
if (x < )
{
putchar('-');
x = -x;
}
if (x > ) write(x/);
putchar(x%+'');
}
template <typename T> inline void writeln(T x)
{
write(x);
puts("");
}
inline void add(int u,int v,long long w)
{
tot++;
e[tot] = (Edge){v,w,head[u]};
head[u] = tot;
}
inline long long spfa()
{
int i,cur,v;
long long w,ans = ;
queue<int> q;
static bool inq[MAXN];
static int cnt[MAXN];
q.push();
inq[] = true;
cnt[] = ;
while (!q.empty())
{
cur = q.front();
q.pop();
inq[cur] = false;
for (i = head[cur]; i; i = e[i].nxt)
{
v = e[i].to;
w = e[i].w;
if (dis[cur] + w > dis[v])
{
dis[v] = dis[cur] + w;
if (!inq[v])
{
inq[v] = true;
q.push(v);
cnt[v]++;
if (cnt[v] > n) return -;
}
}
}
}
for (i = ; i <= n; i++) ans += dis[i];
return ans;
} int main()
{ read(n); read(k);
for (i = n; i >= ; i--) add(,i,);
for (i = ; i <= k; i++)
{
read(x); read(a); read(b);
if (x == )
{
add(a,b,);
add(b,a,);
}
if (x == )
{
add(a,b,);
if (a == b)
{
writeln(-);
return ;
}
}
if (x == ) add(b,a,);
if (x == )
{
add(b,a,);
if (a == b)
{
writeln(-);
return ;
}
}
if (x == ) add(a,b,);
}
writeln(spfa()); return ; }