acwing-385. GF和猫咪的玩具

考点

• 最短路

题解

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e2 + 50;
int n, m, d[maxn][maxn];

int main() {
  cin >> n >> m;
  // 正环没有最长路，和负环没有最短路一样，可以无限循环
  memset(d, 0x3f, sizeof(d));
  for (int i = 1; i <= n; ++i) d[i][i] = 0;
  for (int u, v, i = 1; i <= m; ++i) {
    cin >> u >> v;
    d[u][v] = d[v][u] = 1;
  }
  for (int k = 1; k <= n; ++k) {
    for (int i = 1; i <= n; ++i) {
      for (int j = 1; j <= n; ++j) {
        d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
      }
    }
  }
  int ans = 0;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      ans = max(ans, d[i][j]);
    }
  }
  cout << ans << endl;
  return 0;
}

思路

绳索可以抽象为一条边权为1的双向边，代表数量1，其余部分设置为极大值，然后用floyd求任意两点间最短路。

不要妄图求最长路！你在正环求最长路、负环求最短路都是逻辑错误，因为根本上可以无限循环！

顺带解释一下题意，以样例举例，1 - 2 - 4 - 3 - 5 - 6 - 1拉紧1和4时只有1 - 2 - 4是紧的，其余部分都是松的，所以才要去找最短路，因为一个环的结果只由短的那部分决定。