| 33 | public static int ans1, ans2, ans3; |
| 34 | |
| 35 | public static void compute() { |
| 36 | // 设置初始关系 |
| 37 | for (int i = 1; i <= n; i++) { |
| 38 | for (int j = 1; j <= n; j++) { |
| 39 | if (s[i][j] == '=') { |
| 40 | dmin[i][j] = 0; |
| 41 | dmax[i][j] = 0; |
| 42 | } else if (s[i][j] == '+') { |
| 43 | dmin[i][j] = 1; |
| 44 | dmax[i][j] = 2; |
| 45 | } else if (s[i][j] == '-') { |
| 46 | dmin[i][j] = -2; |
| 47 | dmax[i][j] = -1; |
| 48 | } else { |
| 49 | dmin[i][j] = -2; |
| 50 | dmax[i][j] = 2; |
| 51 | } |
| 52 | } |
| 53 | } |
| 54 | for (int i = 1; i <= n; i++) { |
| 55 | dmin[i][i] = 0; |
| 56 | dmax[i][i] = 0; |
| 57 | } |
| 58 | // 来自讲解065，Floyd算法 |
| 59 | for (int bridge = 1; bridge <= n; bridge++) { |
| 60 | for (int i = 1; i <= n; i++) { |
| 61 | for (int j = 1; j <= n; j++) { |
| 62 | dmin[i][j] = Math.max(dmin[i][j], dmin[i][bridge] + dmin[bridge][j]); |
| 63 | dmax[i][j] = Math.min(dmax[i][j], dmax[i][bridge] + dmax[bridge][j]); |
| 64 | } |
| 65 | } |
| 66 | } |
| 67 | // 统计答案 |
| 68 | ans1 = ans2 = ans3 = 0; |
| 69 | for (int i = 1; i <= n; i++) { |
| 70 | for (int j = 1; j < i; j++) { |
| 71 | if (i != a && i != b && j != a && j != b) { |
| 72 | if (dmin[a][i] > dmax[j][b] || dmin[a][j] > dmax[i][b]) { |
| 73 | ans1++; |
| 74 | } |
| 75 | if (dmax[a][i] < dmin[j][b] || dmax[a][j] < dmin[i][b]) { |
| 76 | ans3++; |
| 77 | } |
| 78 | if (dmin[a][i] == dmax[a][i] && dmin[j][b] == dmax[j][b] && dmin[a][i] == dmin[j][b]) { |
| 79 | ans2++; |
| 80 | } else if (dmin[b][i] == dmax[b][i] && dmin[j][a] == dmax[j][a] && dmin[b][i] == dmin[j][a]) { |
| 81 | ans2++; |
| 82 | } |
| 83 | } |
| 84 | } |
| 85 | } |
| 86 | } |
| 87 | |
| 88 | public static void main(String[] args) throws IOException { |
| 89 | BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); |