Link: link.

C - Crowd Control

Meaning:

given n n n points m m For an undirected graph with m edges, each edge has a capacity from the starting point 0 0 0 to end n − 1 n-1 The capacity of n − 1 depends on the minimum capacity on the path. In order to maximize the capacity from the start point to the end point, some edges need to be deleted to facilitate from the start point to the end point 0 0 0 walk to n − 1 n-1 The minimum capacity of n − 1 is the largest, and the number of deleted edges is output from small to large

Idea:

First set s p f a spfa spfa maximizes the minimum edge and records the path from 0 0 0 to n − 1 n-1 After the path of n − 1 is saved, it passes through a double cycle, or d f s dfs dfs writes down all the edges that are not on the corresponding path, and then sorts them to re output. Because the chained forward star stores undirected edges, it is OK to find the answer according to one edge, so it is i + = 2 i+=2 i+=2, the number of the side is the number in the chain forward star / 2 /2 /2
You can also pass two points + B F S +BFS +BFS to maximize the minimum edge, then find the path, and then delete the non path edge, or the maximum spanning tree
Link: link.

#include <bits/stdc++.h>
using namespace std;
const int N = 2e4 + 10;
const int inf = 0x7fffffff;
int ue[N], h[N], e[N], ne[N], w[N], idx;
int dis[N], vis[N], pre[N];
int n, m;
int st, ed;
vector<int> path;
vector<int> res;
void add_edge(int a, int b, int c) {
    ue[idx] = a;
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

void spfa() {
    memset(dis, 0, sizeof(dis));
    queue<int> q;
    q.push(st);
    dis[st] = inf;
    vis[st] = 1;
    while (!q.empty()) {
        int t = q.front();
        q.pop();
        vis[t] = 0;
        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            if (dis[j] < min(dis[t], w[i])) {
                dis[j] = min(dis[t], w[i]);
                pre[j] = t;
                if (!vis[j]) {
                    vis[j] = 1;
                    q.push(j);
                }
            }
        }
    }
}
void dfs1(int u) {
    path.push_back(u);
    vis[u] = 1;
    if (u == 0) return;
    dfs1(pre[u]);
}

void dfs2(int n) {
    int now = path[n];
    if (n == 0) {
        for (int i = 0; i < idx; i += 2) {
            if (ue[i] == now && e[i] != path[n + 1] ||
                e[i] == now && ue[i] != path[n + 1]) {
                res.push_back(i / 2);
            }
        }
        return;
    } else {
        for (int i = 0; i < idx; i += 2) {
            if (ue[i] == now && e[i] != path[n + 1] && e[i] != path[n - 1] ||
                e[i] == now && ue[i] != path[n + 1] && ue[i] != path[n - 1]) {
                res.push_back(i / 2);
            }
        }
        dfs2(n - 1);
    }
}
int main() {
    memset(h, -1, sizeof(h));
    scanf("%d%d", &n, &m);
    for (int i = 0, a, b, c; i < m; i++) {
        scanf("%d%d%d", &a, &b, &c);
        add_edge(a, b, c);
        add_edge(b, a, c);
    }
    st = 0, ed = n - 1;
    spfa();
    memset(vis, 0, sizeof(vis));
    dfs1(ed);
    dfs2(path.size() - 1);

    sort(res.begin(), res.end());
    res.erase(unique(res.begin(), res.end()), res.end());

    if (res.size() == 0) {
        puts("none");
    } else {
        for (int i = 0; i < res.size(); i++) {
            printf("%d ", res[i]);
        }
    }
}

A - Abandoned Animal

Meaning:

given n n The location number of n supermarkets and the goods they sell are now given a copy m m The list of purchased goods in line m asks whether the path taken by shopping in the order listed in the list is unique, uncertain or nonexistent

Idea:

Open two-dimensional v e c t o r vector vector to store the relationship between supermarkets and commodities. First, if multiple stores meet the conditions in the list order, priority will be given to the nearest store. Then, if multiple commodities meet the conditions in the list order, and the store farthest from Youxian District, then see whether the paths of the two traversal methods are the same. If the traversal fails, it does not exist, If the paths are the same, they are unique, and if they are different, they are uncertain

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
vector<int> shop[N];
map<string, int> mp;
int a[N];
char s[20];
int n, k, m;
int id;
int idx = 1;
vector<int> pre;
vector<int> suf;
int main() {
    cin >> n >> k;

    for (int i = 0; i < k; i++) {
        scanf("%d%s", &id, s);
        if (mp[s]) {
            shop[id].push_back(mp[s]);
        } else {
            mp[s] = idx;
            shop[id].push_back(idx++);
        }
    }
    cin >> m;
    for (int i = 0; i < m; i++) {
        scanf("%s", s);
        a[i] = mp[s];
    }

    int cur = 0;
    int flag = 0;

    for (int i = 0; i < n && cur < m; i++) {
        int len = shop[i].size();

        for (int j = 0; j < len; j++) {
            if (shop[i][j] == a[cur]) {
                pre.push_back(i);
                cur++;
                i--;
                break;
            }
        }
    }

    if (pre.size() == m) {
        flag++;
    }

    cur = m - 1;

    for (int i = n - 1; i >= 0 && cur >= 0; i--) {
        int len = shop[i].size();
        for (int j = len - 1; j >= 0; j--) {
            if (shop[i][j] == a[cur]) {
                suf.push_back(i);
                cur--;
                i++;
                break;
            }
        }
    }

    if (suf.size() == m) {
        flag++;
    }

    if (flag == 0) {
        puts("impossible");
    } else if (flag == 1) {
        puts("unique");
    } else {
        bool f = 0;
        reverse(suf.begin(), suf.end());
        for (int i = 0; i < m; i++) {
            if (pre[i] != suf[i]) {
                f = 1;
                break;
            }
        }
        if (f)
            puts("ambiguous");
        else
            puts("unique");
    }

    return 0;
}

To be continued
If you have any suggestions or criticisms and additions, please leave a message and point it out. Thank you very much