图算法和图模型(六)

spfa判负环,差分约束系统
状态图,隐式图等等
图论最短路算法中一些比较精彩的应用

差分约束

$\textbf{algorithm: system of diffrence constraints}$
$\textbf{i)} \quad \forall i, j , \quad x_j - x_i \leqslant b_k$
$\quad \quad \Longrightarrow w(i, j) = b_k$
$\quad \quad \textbf{let src, } \forall u \in V(G), w(src, u) = 0$
$\textbf{ii)}\quad \text{run } \textbf{spfa}()$
$\quad \quad \textbf{if negative cycle exists, } \text{solution}=\emptyset$
$\quad \quad \textbf{if no nega-cycle, } \text{solution = } [\cdots]$

$\textbf{proof}$
$\quad \forall e(u, v), \quad l(v) > l(u) + w(u, v)$
$\quad \sum l(v) > \sum l(u) + \sum w(u, v) , \quad \sum w(u, v) < 0 $
$\quad \Rightarrow \sum l(v) = \sum l(u)$

$\quad \forall u \in V(G), \text{bellman-Ford never stop, no solution}$

$\textbf{problem}$
$\text{以 } v \text{ 为终点的边权值减小 } k, \text{ 以 } v \text{ 为起点的边权值增加 }k$
$\text{变化后所有边的权值非负,并且尽量大}$

$\textbf{algorithm: binary-search}$
$\text{satisfy system, spfa() return true}$
$\text{not satisfy system, spfa() return false}$
$\textbf{if and only if no} \text{ nega-Cycle, satisfy}$

$\quad \textbf{ if spfa}(x_{\max} + 1)=\textbf{true, solution} = \infty$
$\quad \textbf{ if spfa}(x_{\min}) = \textbf{false, solution} = \emptyset$
$\quad \text{ check mid}(x_{\min}, x_{\max}) \Leftrightarrow \text{mid}(L, R)$
$\quad \quad \textbf{ if mid } \text{satisfy }, L = \text{mid}, \textbf{mid } \uparrow$
$\quad \quad \textbf{ else } R = \text{mid}, \textbf{ mid } \downarrow$

思路还是常见的二分,如果中间值满足
就尝试增加中间值,让它尽可能往 $\textbf{not satisfy}$ 方向靠
直到不满足为止

否则,就减小中间值,让它更容易 $\textbf{satisfy}$

UVA11478

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
const int maxn = 500 + 10;
const int inf = 0x3f3f3f3f;
int n, m;

// == Graph definition ==
vector<int> G[maxn];

class Edge {
public:
int to, weight;
Edge() {}
Edge(int t, int w) : to(t), weight(w) {}
};

vector<Edge> edges;

void initG() {
edges.clear();
_for(i, 0, maxn) G[i].clear();
}

void addEdge(int u, int v, int w) {
edges.push_back(Edge(v, w));
G[u].push_back(edges.size() - 1);
}
// == Graph finished ==
int cnt[maxn], inq[maxn];
int D[maxn];

void initSPFA() {
Set(cnt, 0);
Set(inq, 0);
Set(D, inf);
}

// true: nega-cycle
// false: non-negaCycle
int spfa() {
initSPFA();
queue<int> que;
_rep(i, 1, n) {
D[i] = 0;
que.push(i);
inq[i] = true;
}

while (!que.empty()) {
int x = que.front();
que.pop();
inq[x] = 0;

_for(i, 0, G[x].size()) {
const Edge& e = edges[G[x][i]];
int y = e.to;

if(D[y] > D[x] + e.weight) {
D[y] = D[x] + e.weight;
if(!inq[y]) {
que.push(y);
inq[y] = true;

if(++cnt[y] > n) return true;
}
}
}
}
return false;
}

bool check(int x) {
_for(i, 0, edges.size()) {
edges[i].weight -= x;
}
bool ret = spfa();
_for(i, 0, edges.size()) {
edges[i].weight += x;
}

return !ret;
}

int main() {
freopen("input.txt", "r", stdin);
while (scanf("%d%d", &n, &m) == 2) {
initG();

// build graph
int ud = 0;
_for(i, 0, m) {
int u, v, d;
scanf("%d%d%d", &u, &v, &d);
addEdge(u, v, d);
ud = max(ud, d);
}
// build finished
// x in [1, ud]
//debug(ud);

if(check(ud + 1)) printf("Infinite\n");
else if(!check(1)) printf("No Solution\n");
else {
int ans = 1;
int L = 2, R = ud;

while (L <= R) {
int mid = (L + R) >> 1;
//debug(mid);
if(check(mid)) {
ans = mid;
L = mid + 1;
}
else R = mid - 1;
}
printf("%d\n", ans);
}
}
}

状态图编码问题

以 $\textbf{colored cubes} 为例$
colored-cubes

群运算观点下的图形变换

POJ2741

$\text{change posture of cubes}$
改变 $\textbf{cubes}$ 的 $\textbf{posture}$
本质是一个$\textbf{置换(permutation)}$

由 $\Omega \rightarrow \Omega$ 的变换组成的集合称为置换
$S_n = S(\Omega)$

$\textbf{i) } S_n \text{ 的单位元定义: } \forall \pi \in S_n, \ \pi e = \pi = e\pi$
$\quad e:= \textbf{for } \forall i \in [1, n]$
$\quad \quad \quad A(i) = i$

$\textbf{ii) } \pi: i \mapsto \pi(i), i = 1, 2, \cdots, n$

其本质是构成了一个$\textbf{全排列映射}$

$\textbf{iii) } S_n \text{上的乘法运算其实是置换的合成}$
$\quad \text{ 构成了} \textbf{ n 元对称群}$

$\textbf{example}$
colored-cubes02

$\textbf{algorithm1}$
$\textbf{permutation groups}$
$\textbf{i) for } \forall i \in [1, n], e:\Rightarrow A(i) = i$
$\textbf{ii) }$

$\quad \textbf{for } \forall i \in [1, n], \textbf{let } e = [A(i)]$
$\quad \quad \text{eg: }\quad \pi_{\textbf{left}}(i) = p$
$\quad \quad D=\pi^{k} = (\pi_k\pi_{k-1}\cdots \pi_2\pi_1) e$
$\quad \quad D(i) = \textbf{trans(A(i))}, \text{ return } D$

$\textbf{algorithm2 逆运算}$

$\textbf{permutation inversion}$
$\quad \textbf{for } \forall x \in [1, n]$
$\quad \quad \ \pi(x) = p$
$\quad \quad \ \textbf{do } A(p) \gets A(x)$

$\textbf{main algorithm}$

$\textbf{check()}$
$\text{get inversion: } ori(i) \gets cube(i)$

$\textbf{for } \forall k \in \textbf{faces}[0, 1, \cdots, 5], \textbf{tot} = 0$
$\quad \text{ get }\textbf{ Max-color}$
$\quad \textbf{ for } \forall i \in \textbf{ori}[1, \cdots, n]$
$\quad \quad \textbf{ Max-color=} \max(\textbf{Max-color}, \textbf{ cnt}(ori(i, k)))$
$\quad \textbf{ tot} = \sum (n - \textbf{colored-Max-face})$
$\textbf{ans = } \min(\textbf{ans, tot})$

$\textbf{dfs}(d)$
$\quad \ \textbf{for } \forall i \in [0, 23)$
$\quad \quad \ \text{cube(d) shapes as } \textbf{posture } R(d) = i$
$\quad \quad \ \textbf{dfs}(d + 1)$

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
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185

// == enumerate permutation ==
/*
int LEFT[] = {4, 0, 2, 3, 5, 1};
int UP[] = {2, 1, 5, 0, 4, 3};

void rot(int *trans, int *A) {
int q[6];
memcpy(q, A, sizeof(q));
_for(i, 0, 6) A[i] = trans[q[i]];
}

void enumerate() {
int E[6] = {0, 1, 2, 3, 4, 5};

_for(i, 0, 6) {
int A[6];
memcpy(A, E, sizeof(E));
if(i == 0) rot(UP, A);
if(i == 1) {
rot(LEFT, A);
rot(UP, A);
}
if(i == 3) {
rot(UP, A);
rot(UP, A);
}
if(i == 4) {
rot(LEFT, A);
rot(LEFT, A);
rot(LEFT, A);
rot(UP, A);
}
if(i == 5) {
rot(LEFT, A);
rot(LEFT, A);
rot(UP, A);
}

_for(k, 0, 4) {
printf("{%d, %d, %d, %d, %d, %d},\n", A[0], A[1], A[2], A[3], A[4], A[5]);
rot(LEFT, A);
}
}
}
// == enumerate finsihed ==

int main() {
freopen("out.txt", "w", stdout);
enumerate();
}
*/

/*
{2, 1, 5, 0, 4, 3},
{2, 0, 1, 4, 5, 3},
{2, 4, 0, 5, 1, 3},
{2, 5, 4, 1, 0, 3},
{4, 2, 5, 0, 3, 1},
{5, 2, 1, 4, 3, 0},
{1, 2, 0, 5, 3, 4},
{0, 2, 4, 1, 3, 5},
{0, 1, 2, 3, 4, 5},
{4, 0, 2, 3, 5, 1},
{5, 4, 2, 3, 1, 0},
{1, 5, 2, 3, 0, 4},
{5, 1, 3, 2, 4, 0},
{1, 0, 3, 2, 5, 4},
{0, 4, 3, 2, 1, 5},
{4, 5, 3, 2, 0, 1},
{1, 3, 5, 0, 2, 4},
{0, 3, 1, 4, 2, 5},
{4, 3, 0, 5, 2, 1},
{5, 3, 4, 1, 2, 0},
{3, 4, 5, 0, 1, 2},
{3, 5, 1, 4, 0, 2},
{3, 1, 0, 5, 4, 2},
{3, 0, 4, 1, 5, 2},
*/


const int D[24][6] = {
{2, 1, 5, 0, 4, 3},
{2, 0, 1, 4, 5, 3},
{2, 4, 0, 5, 1, 3},
{2, 5, 4, 1, 0, 3},
{4, 2, 5, 0, 3, 1},
{5, 2, 1, 4, 3, 0},
{1, 2, 0, 5, 3, 4},
{0, 2, 4, 1, 3, 5},
{0, 1, 2, 3, 4, 5},
{4, 0, 2, 3, 5, 1},
{5, 4, 2, 3, 1, 0},
{1, 5, 2, 3, 0, 4},
{5, 1, 3, 2, 4, 0},
{1, 0, 3, 2, 5, 4},
{0, 4, 3, 2, 1, 5},
{4, 5, 3, 2, 0, 1},
{1, 3, 5, 0, 2, 4},
{0, 3, 1, 4, 2, 5},
{4, 3, 0, 5, 2, 1},
{5, 3, 4, 1, 2, 0},
{3, 4, 5, 0, 1, 2},
{3, 5, 1, 4, 0, 2},
{3, 1, 0, 5, 4, 2},
{3, 0, 4, 1, 5, 2}
};

// D[r[i]] get posture of ith cube

int n;
const int maxn = 4;
int ori[maxn][6];
int cube[maxn][6];
int r[maxn];
int ans;
vector<string> data;

void init() {
ans = n * 6;
data.clear();
Set(r, 0);
}

inline int getID(const char *name) {
string str(name);
_for(i, 0, data.size()) {
if(data[i] == str) return i;
}
data.push_back(str);
return data.size() - 1;
}

// == check ==
void inv(int ori[][6], const int cube[][6]) {
_for(i, 0, n) _for(j, 0, 6) {
int p = D[r[i]][j];
ori[i][p] = cube[i][j];
}
}

void check() {
inv(ori, cube);

int tot = 0;
_for(k, 0, 6) {
int Max = 0;
int cnt[maxn * 6];
Set(cnt, 0);
_for(i, 0, n) Max = max(Max, ++cnt[ori[i][k]]);
tot += n - Max;
}
ans = min(ans, tot);
}
// == check finished ==

// == dfs ==
void dfs(int d) {
if(d == n) check();
else {
_for(i, 0, 24) {
r[d] = i;
dfs(d + 1);
}
}
}
// == dfs finished ==

int main() {
freopen("input.txt", "r", stdin);
while (scanf("%d", &n) == 1 && n) {
init();

// get data of cubes
_for(i, 0, n) _for(j, 0, 6) {
char name[30];
scanf("%s", name);
cube[i][j] = getID(name);
}

dfs(1);

printf("%d\n", ans);
}
}

状态空间建图

UVALive4128

$\textbf{i) state transition equation}$
LA4128

$\textbf{ii) start and end state}$
LA4128

$\textbf{algorithm}$
$\textbf{i) hash-coding for every state}$
$\quad \textbf{for } \forall dir, \quad \text{add(0, }\textbf{Hash}(r_1, c_1, dir, 1), cost)$
$\quad \textbf{for } \forall \textbf{r, c}, \text{ according to equation}$
$\quad \quad \textbf{ u}(r,c), \textbf{v}(nr, nc)$
$\quad \quad \textbf{ add}(\textbf{Hash}(\textbf{u}, dir, doubled), \textbf{Hash}(\textbf{v}, nDir, nDoubled), cost)$

$\textbf{ii) run } Dijkstra()$
$\quad \quad \textbf{for } \forall dir \in[0, 4), \forall doubled \in [0,2)$
$\quad \quad \quad \text{ get } \min\textbf{D}(\text{Hash}(\text{end},dir, double))$

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
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180

const int dr[] = {-1, 0, 1, 0};
const int dc[] = {0, -1, 0, 1};
const int UP = 0, LEFT = 1, DOWN = 2, RIGHT = 3;
const int inv[] = {2, 3, 0, 1};

const int maxn = 100 + 5;
int R, C, r1, c1, r2, c2;
int cost[maxn][maxn][4];
int N;
const int maxN = maxn * maxn * 8 + 5;
const int inf = 0x3f3f3f3f;

inline int read() {
int x;
scanf("%d", &x);
return x;
}

// == Graph defintion ==
vector<int> G[maxN];

class Edge {
public:
int from, to, weight;
Edge() {}
Edge(int f, int t, int w) : from(f), to(t), weight(w) {}
};

vector<Edge> edges;

class Node {
public:
int u, dist;
bool operator< (const Node& rhs) const {
return dist > rhs.dist;
}

Node() {}
Node(int u, int d) : u(u), dist(d) {}
};

void initG() {
edges.clear();
_for(i, 0, maxN) G[i].clear();
}

void addEdge(int u, int v, int w) {
edges.push_back(Edge(u, v, w));
G[u].push_back(edges.size() - 1);
}
// == Graph finsihed ==

// == build data ==
int id[maxn][maxn][4][2];
int tot = 0;

inline int ID(int r, int c, int dir, int doubled) {
int& x = id[r][c][dir][doubled];
if(x != 0) return x;
x = ++tot;
return x;
}

void init() {
tot = 0;
Set(id, 0);
}
// [1, R], [1, C]
inline bool valid(int r, int c, int dir) {
if(r <= 0 || r > R || c <= 0 || c > C) return false;
return cost[r][c][dir] > 0;
}
// == data finished ==

// == build graph ==
void build() {
_for(dir, 0, 4) if(valid(r1, c1, dir)) {
int u = ID(r1+dr[dir], c1+dc[dir], dir, 1);
assert(u >= 1);
int w = cost[r1][c1][dir] * 2;
addEdge(0, u, w);
}

_rep(r, 1, R) _rep(c, 1, C) _for(dir, 0, 4) if(valid(r, c, inv[dir])) {
_for(nDir, 0, 4) if(valid(r, c, nDir)) {
_for(doubled, 0, 2) {
int nr = r + dr[nDir];
int nc = c + dc[nDir];
int w = cost[r][c][nDir];
int nDoubled = 0;

if(nDir != dir) {
nDoubled = 1;
if(!doubled) w += cost[r][c][inv[dir]];
w += cost[r][c][nDir];
}

addEdge(ID(r, c, dir, doubled), ID(nr, nc, nDir, nDoubled), w);
}
}
}
}
// == build finsihed ==

// == dijkstra ==
int D[maxN], vis[maxN];

void initDij(int st) {
Set(D, inf);
D[st] = 0;
Set(vis, 0);
}

void dijkstra(int st) {
initDij(st);
priority_queue<Node> que;
que.push(Node(st, 0));

while (!que.empty()) {
int x = que.top().u;
que.pop();
if(vis[x]) continue;
vis[x] = 1;

_for(i, 0, G[x].size()) {
const Edge& e = edges[G[x][i]];
int y = e.to;

if(D[y] > D[x] + e.weight) {
D[y] = D[x] + e.weight;
que.push(Node(y, D[y]));
}
}
}
}
// == dijkstra finsihed ==

// == solve ==
void solve(int& ans) {
_for(dir, 0, 4) _for(doubled, 0, 2) {
int ed = ID(r2, c2, dir, doubled);
int res = D[ed];
if(!doubled) res += cost[r2][c2][inv[dir]];
ans = min(ans, res);
}
}
// == solve finsihed ==

int main() {
freopen("input.txt", "r", stdin);
int kase = 0;
while (scanf("%d%d%d%d%d%d", &R, &C, &r1, &c1, &r2, &c2) == 6 && R) {
init();
initG();

// input grid data
_rep(r, 1, R) {
_rep(c, 1, C - 1) cost[r][c][RIGHT] = cost[r][c+1][LEFT] = read();
if(r != R) {
_rep(c, 1, C) cost[r][c][DOWN] = cost[r+1][c][UP] = read();
}
}
N = R*C*8 + 1;

// build graph
build();

// run dijkstra
dijkstra(0);

// solve
int ans = inf;
solve(ans);

printf("Case %d: ", ++kase);
if(ans == inf) printf("Impossible\n");
else printf("%d\n", ans);
}
}

差分dp

差分约束可以解决一系列有条件约束的dp问题
0/1 背包,完全背包等等

Problem Scores

$\text{比如说从一类物品中,每次选一个物品}, \textbf{可以重复}$
$\text{问有多少种选择方法}$
$在此基础上,加入约束条件,就是差分约束dp$

$\textbf{algorithm1: dp()}$

$\textbf{0-1 背包}$

$(i-1) \xrightarrow{update()} (i)$
$\textbf{for } \forall j = n \textbf{ downto } V_i$

$\textbf{完全背包}$

$(i) \xrightarrow{update()} (i\textbf{th itself})$
$\textbf{for } \forall j = V_i \textbf{ to } n$

dp
一个是用以前的阶段更新现在阶段
一个是用当前阶段更新当前
所以循环的顺序是不一样的

$\textbf{algorithm2}$
$1 \leqslant a_i \leqslant n, \forall k, 1 \leqslant k < n $
都有对任意大小为 $k$ 的子集 $S$ 和大小为 $k+1$ 的子集 $T$

这样的集合有多少个?

$\textbf{i) }$

$\textbf{所以只要有 } k = \lfloor \frac{n}{2} \rfloor \textbf{ 成立,所有情况都成立}$

$\textbf{ii) 差分数组的构造}$

$\textbf{if } n = \textbf{odd number}, \lfloor \frac{n}{2} \rfloor = \frac{n-1}{2}$

$\textbf{if } n = \textbf{even number}, \lfloor \frac{n}{2} \rfloor = \frac{n}{2}$

$\textbf{iii)}$
综上所述

$i = 1, C_1 = -1 <0$
$\sum \Delta a_i + 1 \leqslant n$

由此原问题转换为求满足条件 $a_1$ 的个数

$\textbf{iv) algorithm} $

$\quad \textbf{ calculate } f(i), \textbf{使用完全背包}$
$\quad \text{ 此时从 } \forall i \in[2, n] \text{ 的物品中选 }$
$\quad \text{ 第 } i \text{ 个物品重量为 } B_i = C_i + 1$
$\quad \text{ 可以重复选, 每种物品可以选 } a_i \text{次}$
$\quad \text{ 其中背包总重量不超过 }n-1, \text{ 求方案数}$

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
const int maxn = 5000 + 10;
int n, m;
int f[maxn], C[maxn];

void initDP() {
Set(f, 0);
f[0] = 1;

int mid = n >> 1;
_rep(i, 2, mid + 1) C[i] = i - 1;
_rep(i, mid + 2, n) C[i] = n - i + 2;
}

int dp() {
initDP();

_rep(i, 2, n) _rep(j, C[i], n - 1) {
f[j] = (f[j] + f[j - C[i]]) % m;
}

ll ans = 0;
_rep(i, 0, n - 1) {
ans = ans + 1ll * (n - i) * f[i] % m;
ans %= m;
}
return ans;
}

int main() {
freopen("input.txt", "r", stdin);
scanf("%d%d", &n, &m);

int res = dp();
cout << res << endl;
}