< 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#includeusing 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#includeusing 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");}}}
【3算法模板：搜索（6）：做题积累】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
