算法模板（3）：搜索（6）：做题积累

算法模板（3）：搜索（6）：做题积累 一、DFS 1. 1113. 红与黑

有一间长方形的房子，地上铺了红色、黑色两种颜色的正方形瓷砖。你站在其中一块黑色的瓷砖上，只能向相邻（上下左右四个方向）的黑色瓷砖移动。请写一个程序，计算你总共能够到达多少块黑色的瓷砖。

#include
#include
#include
using namespace std;
const int maxn = 25;
char mz[maxn][maxn];
int N, M, sx, sy, tx, ty, dx[] = { 1, -1, 0, 0 }, dy[] = {0, 0, 1, -1};
bool vis[maxn][maxn];
int dfs(int x, int y) {int cnt = 1;vis[x][y] = true;for (int i = 0; i < 4; i++) {int nx = x + dx[i], ny = y + dy[i];if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;if (vis[nx][ny] || mz[nx][ny] != '.') continue;cnt += dfs(nx, ny);}return cnt;
}
int main() {while (cin >> M >> N && N) {memset(vis, false, sizeof vis);for (int i = 0; i < N; i++) {cin >> mz[i];}int sx, sy;for (int i = 0; i < N; i++) {for (int j = 0; j < M; j++) {if (mz[i][j] == '@') {sx = i, sy = j;break;}}}cout << dfs(sx, sy) << endl;}return 0;
}

2. of the Bone

#include
#include
#include
#include
using namespace std;
char g[10][10];
bool vis[10][10];
int N, M, t, sx, sy, gx, gy;
int dx[] = { 1, -1, 0, 0 }, dy[] = { 0, 0, 1, -1 };
bool dfs(int x, int y, int total) {if (total > t) return false;if (total == t && g[x][y] == 'D') return true;//奇偶性剪枝（可行性剪枝）if (abs(t - total - abs(x - gx) - abs(y - gy)) & 1) return false;vis[x][y] = true;for (int i = 0; i < 4; i++) {int nx = x + dx[i], ny = y + dy[i];if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;if (g[nx][ny] == 'X' || vis[nx][ny]) continue;if (dfs(nx, ny, total + 1)) return true;}vis[x][y] = false;return false;
}
int main() {while (cin >> N >> M >> t, N) {memset(vis, false, sizeof vis);int block = 0;for (int i = 0; i < N; i++) cin >> g[i];for (int i = 0; i < N; i++) {for (int j = 0; j < M; j++) {if (g[i][j] == 'S') sx = i, sy = j;else if (g[i][j] == 'D') gx = i, gy = j;else if (g[i][j] == 'X') block++;}}if (N * M - block < t || abs(abs(sx - gx) + abs(sy - gy) - t) & 1) printf("NO\n");else if (dfs(sx, sy, 0)) printf("YES\n");else printf("NO\n");}return 0;
}

3. 1116. 马走日

#include
#include
#include
using namespace std;
int N, M, sx, sy, ans;
int dy[] = { -2, -1, 1, 2, 2, 1, -1, -2 }, dx[] = { -1, -2, -2, -1, 1, 2, 2, 1 };
bool vis[15][15];
void dfs(int x, int y, int cnt) {if (cnt == N * M) {ans++;return;}vis[x][y] = true;for (int i = 0; i < 8; i++) {int nx = x + dx[i], ny = y + dy[i];if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;if (vis[nx][ny]) continue;dfs(nx, ny, cnt + 1);}vis[x][y] = false;
}
int main() {int T;scanf("%d", &T);while (T--) {scanf("%d%d%d%d", &N, &M, &sx, &sy);ans = 0;dfs(sx, sy, 1);printf("%d\n", ans);}return 0;
}

4. 1117. 单词接龙

#include
using namespace std;
const int maxn = 25;
int g[maxn][maxn], N, ans = 0, used[maxn];
string words[maxn], head;
void dfs(string dragon, int last) {ans = max((int)dragon.size(), ans);used[last]++;for (int i = 0; i < N; i++) {if (g[last][i] && used[i] < 2) {dfs(dragon + words[i].substr(g[last][i]), i);}}used[last]--;
}
int main() {cin >> N;for (int i = 0; i < N; i++) {cin >> words[i];}cin >> head;for (int i = 0; i < N; i++) {for (int j = 0; j < N; j++) {string& s1 = words[i], & s2 = words[j];for (int k = 1; k < min(s1.size(), s2.size()); k++) {if (s1.substr(s1.size() - k, k) == s2.substr(0, k)) {g[i][j] = k;break;}}}}for (int i = 0; i < N; i++) {if (words[i][0] == head[0]){dfs(head + words[i].substr(1), 0);}}cout << ans << endl;return 0;
}

5. 1118. 分成互质组

#include
using namespace std;
const int maxn = 15;
//group存放的是数字的下标
int group[maxn][maxn], p[maxn], N, ans = 10;
bool vis[maxn];
int gcd(int a, int b) {if (b == 0) return a;return gcd(b, a % b);
}
bool check(int g[], int gc, int idx) {for (int i = 0; i < gc; i++) {if (gcd(p[g[i]], p[idx]) > 1) return false;}return true;
}
void dfs(int g, int gc, int tc, int start) {if (g >= ans) return;if (tc == N) {ans = g;return;}bool flag = true;for (int i = start; i < N; i++) {if (!vis[i] && check(group[g], gc, i)) {flag = false;vis[i] = true;group[g][gc] = i;dfs(g, gc + 1, tc + 1, i + 1);vis[i] = false;}}if (flag) dfs(g + 1, 0, tc, 0);}
int main() {scanf("%d", &N);for (int i = 0; i < N; i++) scanf("%d", &p[i]);dfs(1, 0, 0, 0);printf("%d\n", ans);return 0;
}

6. 167. 木棒

#include
#include
#include
#include
using namespace std;
const int maxn = 70;
int w[maxn], N, length, sum;
bool vis[maxn];
bool dfs(int u, int s, int start) {if (length * u == sum) return true;if (s == length) return dfs(u + 1, 0, 0);for (int i = start; i < N; i++) {if (vis[i]) continue;if (s + w[i] > length) continue;vis[i] = true;if (dfs(u, s + w[i], i + 1)) return true;vis[i] = false;if (s == 0) return false;if (s + w[i] == length) return false;int j = i;while (j < N && w[i] == w[j]) j++;i = j - 1;   //注意这里，因为马上要i++了，千万别写成i = j。}return false;
}
int main() {while (cin >> N, N) {memset(vis, false, sizeof vis);//注意，当一个length行不通的时候，vis都会被回溯成false的。sum = 0;for (int i = 0; i < N; i++) {cin >> w[i];sum += w[i];}sort(w, w + N, greater<int>());for (length = 1; ; length++) {if (sum % length == 0 && dfs(0, 0, 0)) {cout << length << endl;break;}}}return 0;
}

7. 181. 回转游戏

15adb54fa5e62901814118aa1791edcb

#include
#include
#include
using namespace std;
int op[8][7]{{0, 2, 6, 11, 15, 20, 22},{1, 3, 8, 12, 17, 21, 23},{10, 9, 8, 7, 6, 5, 4},{19, 18, 17, 16, 15, 14, 13},{23, 21, 17, 12, 8, 3, 1},{22, 20, 15, 11, 6, 2, 0},{13, 14, 15, 16, 17, 18, 19},{4, 5, 6, 7, 8, 9, 10}
};
int opposite[8] = { 5, 4, 7, 6, 1, 0, 3, 2 };
int center[8] = { 6, 7, 8, 11, 12, 15, 16, 17 };
int q[24], path[100];
int f() {int sum[4] = {0};for (int i = 0; i < 8; i++) sum[q[center[i]]]++;int s = 0;for (int i = 1; i <= 3; i++) s = max(s, sum[i]);return 8 - s;
}
void operate(int id) {int head = q[op[id][0]];for (int i = 0; i < 6; i++) q[op[id][i]] = q[op[id][i + 1]];q[op[id][6]] = head;
}
bool dfs(int depth, int max_depth, int last) {if (depth + f() > max_depth) return false;if (f() == 0) return true;for (int i = 0; i < 8; i++) {if (opposite[i] != last) {operate(i);path[depth] = i;if (dfs(depth + 1, max_depth, i)) return true;operate(opposite[i]);}}return false;
}
int main() {while (scanf("%d", &q[0]) && q[0]) {for (int i = 1; i < 24; i++) scanf("%d", &q[i]);int depth = 0;while (!dfs(0, depth, -1)) depth++;if (!depth) printf("No moves needed\n");else {//再次提醒！！ 一定要小心这个输出，循环到 depth - 1 就行！for (int i = 0; i < depth; i++) printf("%c", path[i] + 'A');printf("\n");}printf("%d\n", q[center[1]]);}return 0;
}

二、BFS 1. 八数码

queue<string> que;
unordered_map<string, int> d;
int dx[] = { 0, 0, -1, 1 }, dy[] = { 1, -1, 0, 0 };
string st, ed("12345678x");
int bfs() {d[st] = 0;que.push(st);while (que.size()) {auto s = que.front(); que.pop();int dis = d[s];if (s == ed) return dis;int k = s.find('x');int x = k / 3, y = k % 3;for (int i = 0; i < 4; i++) {int nx = x + dx[i], ny = y + dy[i];if (nx < 0 || nx >= 3 || ny < 0 || ny >= 3) continue;swap(s[x * 3 + y], s[nx * 3 + ny]);if (!d.count(s)) {d[s] = dis + 1;que.push(s);}swap(s[nx * 3 + ny], s[x * 3 + y]);}}return -1;
}

2. 1107. 魔板

#include
using namespace std;
queue<string> que;
unordered_map<string, int> d;
map<string, pair<string, char> > pre;
int dx[] = { 0, 0, -1, 1 }, dy[] = { 1, -1, 0, 0 };
string st("12345678"), ed;
int bfs() {d[st] = 0;que.push(st);pre[st].first = "-1";while (que.size()) {auto s = que.front(); que.pop();if (s == ed) return d[s];string t = s;swap(t[0], t[7]), swap(t[1], t[6]), swap(t[2], t[5]), swap(t[3], t[4]);if (!d.count(t)) {d[t] = d[s] + 1;que.push(t);pre[t] = make_pair(s, 'A');}t = s;swap(t[3], t[2]), swap(t[2], t[1]), swap(t[1], t[0]);swap(t[4], t[5]), swap(t[5], t[6]), swap(t[6], t[7]);if (!d.count(t)) {d[t] = d[s] + 1;que.push(t);pre[t] = make_pair(s, 'B');}t = s;char c = t[1];t[1] = t[6], t[6] = t[5], t[5] = t[2], t[2] = c;if (!d.count(t)) {d[t] = d[s] + 1;que.push(t);pre[t] = make_pair(s, 'C');}}
}
int main() {char c;for (int i = 0; i < 8; i++) {cin >> c;ed += c;}int ans = bfs();string path;for (auto p = pre[ed]; p.first != "-1"; p = pre[p.first]) path += p.second;reverse(path.begin(), path.end());cout << ans << endl;if (path != "") cout << path << endl;return 0;
}

3. 1106. 山峰和山谷

void bfs(int x, int y) {int num = g[x][y];que.push({ x, y });vis[x][y] = true;bool is_peak = true, is_valley = true;while (que.size()) {auto p = que.front(); que.pop();int x = p.first, y = p.second;for (int dx = -1; dx <= 1; dx++) {for (int dy = -1; dy <= 1; dy++) {int nx = x + dx, ny = y + dy;if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;if (g[nx][ny] > num) is_peak = false;else if (g[nx][ny] < num) is_valley = false;else if(!vis[nx][ny]){vis[nx][ny] = true;que.push({ nx, ny });}}}}if (is_peak) peak++;if (is_valley) valley++;
}
void solve() {for (int i = 0; i < N; i++) {for (int j = 0; j < N; j++) {if (!vis[i][j]) bfs(i, j);}}printf("%d %d\n", peak, valley);
}

4. 1098. 城堡问题

int N, M;
int g[maxn][maxn];
bool vis[maxn][maxn];
typedef pair<int, int> P;
queue<P> que;
int dx[] = {0, -1, 0, 1}, dy[] = {-1, 0, 1, 0};
int bfs(int x, int y) {int cnt = 0;que.push({ x, y });vis[x][y] = true;while (que.size()) {auto p = que.front(); que.pop();cnt++;int x = p.first, y = p.second;for (int i = 0; i < 4; i++) {if (g[x][y] >> i & 1) continue;int nx = x + dx[i], ny = y + dy[i];if (nx < 0 || nx >= N || ny < 0 || ny >= M || vis[nx][ny]) continue;vis[nx][ny] = true;que.push({ nx, ny });}}return cnt;
}
void solve() {int cnt = 0, max_size = 0;for (int i = 0; i < N; i++) {for (int j = 0; j < M; j++) {if (!vis[i][j]) {max_size = max(max_size, bfs(i, j));cnt++;}}}printf("%d\n%d\n", cnt, max_size);
}

5. 179. 八数码

#include
#include
#include
#include
#include
#include
using namespace std;
typedef pair<int, string> P;
int f(string s) {int res = 0;for (int i = 0; i < s.size(); i++) {if (s[i] == 'x') continue;int num = s[i] - '1';int sx = num / 3, sy = num % 3, tx = i / 3, ty = i % 3;res += abs(sx - tx) + abs(sy - ty);}return res;
}
string bfs(string start) {char op[10] = "udlr";string end = "12345678x";int dx[] = { -1, 1, 0, 0 }, dy[] = { 0, 0, -1, 1 };priority_queue<P, vector<P>, greater<P>> que;unordered_map<string, int> d;unordered_map<string, pair<char, string>> pre;que.push(P(f(start), start));d[start] = 0;while (que.size()) {auto p = que.top(); que.pop();string state = p.second; int dis = p.first;if (state == end) break;int id = state.find('x');int x = id / 3, y = id % 3;for (int i = 0; i < 4; i++) {int nx = x + dx[i], ny = y + dy[i];if (nx < 0 || nx >= 3 || ny < 0 || ny >= 3) continue;string t = state;swap(t[nx * 3 + ny], t[x * 3 + y]);if (!d.count(t) || d[t] > d[state] + 1) {d[t] = d[state] + 1;que.push(P(f(t) + d[t], t));pre[t] = make_pair(op[i], state);}}}string path, now = end;while (now != start) {path += pre[now].first;now = pre[now].second;}reverse(path.begin(), path.end());return path;
}
int main() {char c;string start, nums;for (int i = 0; i < 9; i++) {cin >> c;start += c;if (c != 'x') nums += c;}int cnt = 0;for (int i = 0; i < 8; i++) {for (int j = 0; j < i; j++) {if (nums[j] > nums[i]) cnt++;}}if (cnt & 1) cout << "unsolvable\n";else cout << bfs(start) << endl;return 0;
}

三、图论 1.1126. 最小花费

double bfs() {d[A] = 1;priority_queue<P> que;que.push({ 1, A });while (que.size()) {auto p = que.top(); que.pop();int u = p.second; double dist = p.first;if (vis[u]) continue;vis[u] = true;for (int i = h[u]; i != -1; i = ne[i]) {int v = e[i];if (d[v] < d[u] * w[i]) {d[v] = d[u] * w[i];que.push({ d[v], v });}}}return 100.0 / d[B];
}

8cbad024595760f93e7fc991cebb647a

2.340. 通信线路

#include
#include
#include
#include
using namespace std;
const int maxn = 1010, maxm = 200010, INF = 1e9;
int h[maxn], e[maxm], ne[maxm], idx, w[maxm], N, M, K, d[maxn];
bool vis[maxn];
void add(int a, int b, int c) {e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}
bool bfs(int x) {memset(vis, false, sizeof vis);fill(d, d + maxn, INF);d[1] = 0;deque<int> dq;dq.push_back(1);while (dq.size()) {int u = dq.front(); dq.pop_front();if (u == N) break;if (vis[u]) continue;vis[u] = true;for (int i = h[u]; i != -1; i = ne[i]) {int v = e[i];int cost = (w[i] > x);if (d[v] >= d[u] + cost) {d[v] = d[u] + cost;if (cost) dq.push_back(v);else dq.push_front(v);}}}return d[N] <= K;
}
int main() {memset(h, -1, sizeof h);scanf("%d%d%d", &N, &M, &K);for (int i = 0; i < M; i++) {int a, b, c;scanf("%d%d%d", &a, &b, &c);add(a, b, c);add(b, a, c);}int lb = -1, ub = 1000010;while (ub - lb > 1) {int mid = (lb + ub) / 2;if (bfs(mid)) ub = mid;else lb = mid;}if (ub > 1000000) printf("-1\n");else printf("%d\n", ub);return 0;
}

01分数规划

指的是在图论里面，一堆值之和与另一堆值之和的比值最大，这一般称为01分数规划问题，通常可以用二分去写。

3. 361. 观光奶牛

#include
#include
#include
#include
using namespace std;
const int maxn = 1010, maxm = 5010;
int h[maxn], w[maxm], ver[maxn], e[maxm], ne[maxm], idx;
int N, M, cnt[maxn];
double d[maxn];
bool vis[maxn];
void add(int a, int b, int c) {e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}
bool C(double x) {queue<int> que;memset(cnt, 0, sizeof cnt);for (int i = 1; i <= N; i++) {que.push(i);vis[i] = true;}while (que.size()) {int u = que.front(); que.pop();vis[u] = false;for (int i = h[u]; i != -1; i = ne[i]) {int v = e[i];if (d[v] < d[u] + ver[v] - x * w[i]) {d[v] = d[u] + ver[v] - x * w[i];cnt[v] = cnt[u] + 1;if (cnt[v] >= N) return true;if (!vis[v]) {que.push(v);vis[v] = true;}}}}return false;
}
int main() {memset(h, -1, sizeof h);scanf("%d%d", &N, &M);for (int i = 1; i <= N; i++) scanf("%d", &ver[i]);for (int i = 0; i < M; i++) {int a, b, c;scanf("%d%d%d", &a, &b, &c);add(a, b, c);}double lb = 0, ub = 1000;while(ub - lb > 1e-4) {double mid = (lb + ub) / 2;if (C(mid)) lb = mid;else ub = mid;}printf("%.2f\n", lb);return 0;
}

4. 1165. 单词环

#include
using namespace std;
const int maxn = 700, maxm = 100010;
int h[maxn], w[maxm], e[maxm], ne[maxm], idx;
char edge[1010];
bool vis[maxn];
int N, M;
double d[maxn];
map<string, int> id;
void init() {string ver("__");for (int i = 'a'; i <= 'z'; i++) {for (int j = 'a'; j <= 'z'; j++) {ver[0] = i, ver[1] = j;id[ver] = N++;}}
}
void add(int a, int b, int c) {e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}
bool C(double x) {queue<int> que;for (int i = 0; i < N; i++) {que.push(i);vis[i] = true;}int cnt = 0;while (que.size()) {if (++cnt > 10000) return true;int u = que.front(); que.pop();vis[u] = false;for (int i = h[u]; i != -1; i = ne[i]) {int v = e[i];if (d[v] < d[u] + w[i] - x) {d[v] = d[u] + w[i] - x;if (!vis[v]) {que.push(v);vis[v] = true;}}}}return false;}
int main() {init();string st("__"), ed("__");while (scanf("%d", &M) && M) {memset(h, -1, sizeof h);idx = 0;for (int i = 0; i < M; i++) {scanf("%s", edge);int len = strlen(edge);if (len < 2) continue;st[0] = edge[0], st[1] = edge[1];ed[0] = edge[len - 2], ed[1] = edge[len - 1];int a = id[st], b = id[ed];add(a, b, len);}double lb = 0, ub = 1000;while (ub - lb > 1e-6) {double mid = (lb + ub) / 2;if (C(mid)) lb = mid;else ub = mid;}if(fabs(lb) < 1e-3) printf("No solution\n");else printf("%f\n", lb);}return 0;
}

5. 1125. 牛的旅行

#include
#include
#include
using namespace std;
const int maxn = 160;
const double INF = 1e9, EPS = 1e-3;
int N;
double x[maxn], y[maxn], d[maxn][maxn], max_d[maxn], ans = INF;
char g[maxn][maxn];
bool equal(double x, double y) {return fabs(x - y) <= EPS;
}
double dis(double x1, double y1, double x2, double y2) {return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}
void floyd() {for (int i = 0; i < N; i++) fill(d[i], d[i] + N, INF);for (int i = 0; i < N; i++) {d[i][i] = 0;for (int j = 0; j < i; j++) {if (g[i][j] == '1') d[i][j] = d[j][i] = dis(x[i], y[i], x[j], y[j]);}}for (int k = 0; k < N; k++) {for (int i = 0; i < N; i++) {for (int j = 0; j < N; j++) {d[i][j] = min(d[i][j], d[i][k] + d[k][j]);}}}for (int i = 0; i < N; i++) {for (int j = 0; j < N; j++) {if (!equal(d[i][j], INF)) max_d[i] = max(max_d[i], d[i][j]);}}
}
void solve() {floyd();for (int i = 0; i < N; i++) {for (int j = 0; j < N; j++) {if (equal(d[i][j], INF)) {ans = min(ans, max_d[i] + max_d[j] + dis(x[i], y[i], x[j], y[j]));}}}for (int i = 0; i < N; i++) {ans = max(max_d[i], ans);}printf("%.6f\n", ans);
}
int main() {scanf("%d", &N);for (int i = 0; i < N; i++) {scanf("%lf%lf", &x[i], &y[i]);}for (int i = 0; i < N; i++) {scanf("%s", g[i]);}solve();return 0;
}

6. 传递闭包 343. 排序 矛盾：d[i, i] = 1；唯一确定：d[i, j] 与 d[j, i] (i != j) 有且只有一个是1。若前两种情况都不满足，那么就是顺序不惟一。

#include
#include
#include
#include
using namespace std;
const int INF = 0x3f3f3f3f, maxn = 35;
int g[maxn][maxn], d[maxn][maxn], N, M, type, t;
bool vis[maxn];
void floyd() {memcpy(d, g, sizeof g);for (int k = 0; k < N; k++) {for (int i = 0; i < N; i++) {for (int j = 0; j < N; j++) {d[i][j] |= d[i][k] && d[k][j];}}}
}
int check() {for (int i = 0; i < N; i++) {if (d[i][i]) return 2;}for (int i = 0; i < N; i++) {for (int j = 0; j < i; j++) {if (!d[i][j] && !d[j][i]) return 0;}}return 1;
}
char get_min() {for (int i = 0; i < N; i++) {if (vis[i]) continue;bool flag = true;for (int j = 0; j < N; j++) {if (!vis[j] && d[j][i]) {flag = false;break;}}if (flag) {vis[i] = true;return 'A' + i;}}
}
int main() {while (cin >> N >> M && N) {memset(g, 0, sizeof g);memset(vis, 0, sizeof vis);type = 0;string s;for (int i = 0; i < M; i++) {cin >> s;int a = s[0] - 'A', b = s[2] - 'A';if (!type) {g[a][b] = 1;floyd();type = check();if (type) t = i + 1;}}if (!type) printf("Sorted sequence cannot be determined.\n");else if (type == 2) printf("Inconsistency found after %d relations.\n", t);else {printf("Sorted sequence determined after %d relations: ", t);for (int i = 0; i < N; i++) {printf("%c", get_min());}printf(".\n");}}
}

传递闭包优化

#include
#include
#include
#include
using namespace std;
const int INF = 0x3f3f3f3f, maxn = 35;
int d[maxn][maxn], N, M, type, t;
bool vis[maxn];
int check() {for (int i = 0; i < N; i++) {if (d[i][i]) return 2;}for (int i = 0; i < N; i++) {for (int j = 0; j < i; j++) {if (!d[i][j] && !d[j][i]) return 0;}}return 1;
}
char get_min() {for (int i = 0; i < N; i++) {if (vis[i]) continue;bool flag = true;for (int j = 0; j < N; j++) {if (!vis[j] && d[j][i]) {flag = false;break;}}if (flag) {vis[i] = true;return 'A' + i;}}
}
int main() {while (cin >> N >> M && N) {memset(d, 0, sizeof d);memset(vis, 0, sizeof vis);type = 0;string s;for (int i = 0; i < M; i++) {cin >> s;int a = s[0] - 'A', b = s[2] - 'A';if (!type) {d[a][b] = 1;for (int x = 0; x < N; x++) {if (d[x][a]) d[x][b] = 1;if (d[b][x]) d[a][x] = 1;for (int y = 0; y < N; y++) {if (d[x][a] && d[b][y]) {d[x][y] = 1;}}}type = check();if (type) t = i + 1;}}if (!type) printf("Sorted sequence cannot be determined.\n");else if (type == 2) printf("Inconsistency found after %d relations.\n", t);else {printf("Sorted sequence determined after %d relations: ", t);for (int i = 0; i < N; i++) {printf("%c", get_min());}printf(".\n");}}}

7. 差分约束 1. 393. 雇佣收银员 S i − S i − 1 < = n u m [ i ] S_{i} - S_{i-1}= S_{i-1} Si​>=Si−1​ S i − S i − 8 > = r [ i ] S_i-S_{i-8}>=r[i] Si​−Si−8​>=r[i]， ( i > = 8 ) (i >=8) (i>=8) S i + S 24 − S i + 16 > = r [ i ] S_i+S_{24}-S_{i+16}>=r[i] Si​+S24​−Si+16​>=r[i]， ( 0 < = i < = 7 ) (0