水题笔记_ [SCOI2011]糖果 [差分约束]

代码实现是不可忽视的能力

懵逼的 题目

传送至 (上市的)Bilibili

扯淡的 题解

胡乱写写…

luogu和LOJ蜜汁T…反正b站和vijos老娘过了…心理AC dafa is good

观察不等式$to > from + cost$, 即最长路的更新过程, 更新后将满足这个不等式

而我们的差分约束: $A - B > x \Rightarrow A > b + x$与最长路更新后的结果一模一样…于是我们就可以利用最长路求这个差分约束的一个解, 如果我们设源点$S$的$dis$为$0$的话就是一个最小解

什么? 你说没有源点? 自己造一个源点向所有的点都连上一条$dis = 0$的边不就好了…反正是求最长路…

你问我最短路…不会最短路的边权肯定有负的啊…$dis = 0$也不会影响什么…吧?

沙茶的 代码

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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
// luogu-judger-enable-o2
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#define INF (0x7fffffff)
#define MAXN (100000 + 5)
#define MAXM (100000 + 5)
#define LL long long
#define getchar() (S == T && (T = (S = BB) + fread(BB, 1, MAXN << 5, stdin), S == T) ? EOF : *S++)
char BB[MAXN * 20], *S = BB, *T = BB;
using namespace std;
const int s = 0;
struct edg
{
int from, to, next, cost;
}b[MAXM << 1];
int g[MAXN], cntb, n, m, dis[MAXN], cnt[MAXN];;
bool inq[MAXN];
inline int read()
{
register int c = 0, re = 0;
while (c < '0' || c > '9')
c = getchar();
while (c >= '0' && c <= '9')
{
re = (re << 1) + (re << 3) + (c ^ '0');
c = getchar();
}
return re;
}
inline void adn(const int from, const int to, const int cost)
{
b[++cntb].next = g[from];
b[cntb].from = from;
b[cntb].to = to;
b[cntb].cost = cost;
g[from] = cntb;
}
// to >= from + cost
// to - from >= cost
void spfa()
{
queue<int> q;
dis[s] = 1;
q.push(s);
inq[s] = true;
++cnt[s];
while (!q.empty())
{
int dq = q.front();
q.pop();
inq[dq] = false;
for (int i = g[dq]; i; i = b[i].next)
if (dis[b[i].to] < dis[dq] + b[i].cost)
{
dis[b[i].to] = dis[dq] + b[i].cost;
if (!inq[b[i].to])
{
++cnt[b[i].to];
if (cnt[b[i].to] > n)
{
puts("-1");
exit(0);
}
q.push(b[i].to);
inq[b[i].to] = true;
}
}
}
}
// to >= from + cost
// to - from >= cost
void init()
{
n = read();
int k = read();
// scanf("%d%d", &n, &k);
for (int i = 1; i <= k; i++)
{
int sre = read(), srx = read(), sry = read();
// scanf("%d%d%d", &sre, &srx, &sry);
if (sre == 1)
{
adn(srx, sry, 0);
adn(sry, srx, 0);
}
else if (sre == 2)
adn(srx, sry, 1);
else if (sre == 3)
adn(sry, srx, 0);
else if (sre == 4)
adn(sry, srx, 1);
else if (sre == 5)
adn(srx, sry, 0);
}
}
int main()
{
freopen("in.in", "r", stdin);
freopen("wa.out", "w", stdout);
memset(inq, false, sizeof(inq));
memset(cnt, 0, sizeof(cnt));
init();
memset(dis, 0, sizeof(dis));
for (int i = n; i >= 1; i--)
adn(s, i, 0);
spfa();
LL sum = 0;
for (int i = 1; i <= n; i++)
sum += dis[i];
printf("%lld", sum);
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
*/

By 有些焦虑的 Cansult