1039、1035是今年浙大考研复试上机前，晴神出的模拟题，当时刚好有时间（3月PAT考崩掉没多久，对内容基本还有印象），就做了一下。当时1039最短路最后一个case超时，也没看题解= =，反正自抱自泣嘛。今天再做，还是case5 TLE了。这次总算没逃避，看了题解明白了。总结一下。

1039 | 古剑奇谭三：迷宫救援

本题题意抽象出来就是：求删掉一条边之后的最短路，但是删的是哪条边你不知道，问最坏情况下最短路是多长。
原先的做法挺蠢的，就是map <pair<int, int>, int>存边集，逐一删边Dijkstra，复杂度💥，边数乘Dijkstra的复杂度……于是看了晴神的题解，搬运一下：

1. 先不删边，Dijkstra一次，求出任意一条最短路，用pre数组保存。

2. 删边Dijkstra
   最短路径上最多只有 V-1 条边(V 为顶点数)，因此最多跑 V-1 次最短路算法即可。

   • 若仅有这一条最短路

     • 删掉不在这条路径上的一条边 ，对最短路长度没有影响；
     • 删掉这条路径上的一条边，则最短路长度会变大；

   • 若有多条最短路

     • 对两条没有公共边的最短路径，不管删掉哪条上的边，对从起点到终点的最短距离都不会有影响;

     • 如果两条最短路径有公共边

       • 删除非公共边不会对最短距离产生影响
       • 删除公共边会对最短距离产生影响——要把所有最短路径都求出来呢?不需要，因为公共边是公共的， 只需考虑其中一条最短路径就行。

⚠️pre数组仅在那次不删边Dijkstra中更新！！！之后仅仅是删边的依据，再更新就乱套了……

#include <algorithm>
#include <cstdio>

#define INF 0x3fffffff
using namespace std;
int nn, mm, graph[501][501], dist[501], pre[501], Mdist = -1;
bool visited[501];

void Dijkstra(bool flag) {
    fill(dist, dist + 501, INF);
    fill(visited, visited + 501, false);
    dist[1] = 0;
    for (int i = 0; i < nn; i++) {
        int curr = -1, md = INF;
        for (int j = 1; j <= nn; j++) {
            if (!visited[j] && dist[j] < md)
                md = dist[j], curr = j;
        }
        if (curr == -1 || curr == nn)
            return;
        visited[curr] = true;
        for (int j = 1; j <= nn; j++) {
            if (!visited[j] && graph[curr][j] != INF && dist[curr] + graph[curr][j] < dist[j]) {
                dist[j] = dist[curr] + graph[curr][j];
                if (flag) pre[j] = curr;
            }
        }
    }
}

int main() {
    fill(graph[0], graph[0] + 501 * 501, INF);
    scanf("%d%d", &nn, &mm);
    int v1, v2, weight;
    for (int i = 0; i < mm; i++) {
        scanf("%d%d%d", &v1, &v2, &weight);
        graph[v1][v2] = graph[v2][v1] = weight;
    }
    fill(pre, pre + 501, -1);
    Dijkstra(true);
    int curr = nn, temp;
    while (curr != -1) {
        temp = graph[curr][pre[curr]];
        graph[curr][pre[curr]] = graph[pre[curr]][curr] = INF;
        Dijkstra(false);
        Mdist = max(Mdist, dist[nn]);
        if (Mdist == INF) {
            puts("It's a bug!!!");
            return 0;
        }
        graph[curr][pre[curr]] = graph[pre[curr]][curr] = temp;
        curr = pre[curr];
    }
    printf("%d\n", Mdist);
    return 0;
}

1035 | 稳定婚姻问题

看半天才勉强看懂题。今天有点傻。不要犹豫，按概念模拟就好，二重遍历判断就完事儿了。
注意存储优先级的方式。

#include <cstdio>

int pr1[501][501] = {0}, pr2[501][501] = {0};
using namespace std;

int main() {
    int nn, temp;
    scanf("%d", &nn);
    for (int i = 1; i <= nn; ++i) {
        for (int p = nn; p >= 1; --p) {
            scanf("%d", &temp);
            pr1[i][temp] = p;
        }
    }
    for (int i = 1; i <= nn; ++i) {
        for (int p = nn; p >= 1; --p) {
            scanf("%d", &temp);
            pr2[i][temp] = p;
        }
    }
    int nq, v1, v2;
    scanf("%d", &nq);
    for (int i = 0; i < nq; ++i) {
        int link1[501], link2[501];
        for (int k = 1; k <= nn; ++k) {
            scanf("%d%d", &v1, &v2);
            link1[v1] = v2;
            link2[v2] = v1;
        }
        bool stable = true;
        for (int aa = 1; stable && aa <= nn; ++aa) {
            for (int bb = 1; bb <= nn; ++bb) {
                if (pr1[aa][bb] > pr1[aa][link1[aa]] && pr2[bb][aa] > pr2[bb][link2[bb]]) {
                    stable = false;
                    break;
                }
            }
        }
        puts(stable ? "Stable" : "Not Stable");
    }
    return 0;
}