Bzoj 2330(差分约束)

BZOJ 2330
差分约束。
裸题不讲了。可以看我的差分约束学习笔记。
注意这题直接把所有点加进来做,否则TLE,还要开long long

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#define ms(i,j) memset(i,j, sizeof i);
#define ll long long
using namespace std;
const int MAXN = 100000 + 5;
ll n,k;
struct edge
{
ll u,v,c;
}E[MAXN*4];
ll e_num = 0;
vector<ll> G[MAXN];
void addE(ll u, ll v, ll c)
{
e_num++;
E[e_num].u = u;
E[e_num].v = v;
E[e_num].c = c;
G[u].push_back(e_num);
}
ll dis[MAXN];
ll vi[MAXN];
ll cir[MAXN];
ll spfa()
{
queue<ll> q;
for (ll i=1;i<=n;i++)
{
dis[i] = 1;
vi[i] = false;
cir[i] = 1;
q.push(i);
}
while (!q.empty())
{
ll r = q.front(); q.pop();
for (ll i=0;i<G[r].size();i++)
{
edge ed = E[G[r][i]];
vi[ed.v] = false;
if (dis[ed.v]<dis[r]+ed.c)
{
dis[ed.v] = dis[r]+ed.c;
if (!vi[ed.v])
{
cir[i]++;
if (cir[i]>n)
{
return false;
}
vi[ed.v] = true;
q.push(ed.v);
}
}
}
}
return true;
}
int main()
{
scanf("%d%d", &n, &k);
for (ll i=1;i<=k;i++)
{
ll x,a,b;
scanf("%lld%lld%lld", &x, &a, &b);
switch(x)
{
case 1: addE(a,b,0); addE(b,a,0); break;
case 2: if (a==b) {printf("-1\n");return 0;} addE(a,b,1); break;
case 3: addE(b,a,0); break;
case 4: if (a==b) {printf("-1\n");return 0;} addE(b,a,1); break;
case 5: addE(a,b,0); break;
}
}
if(!spfa()) printf("-1\n"); else
{
ll ans = 0;
for (ll i=1;i<=n;i++)
{
ans += dis[i];
}
printf("%lld\n", ans);
}
return 0;
}

------ 本文结束 ------