题解 UOJ134 【[UR #9] App 管理器】

Leasier · 2023-07-15 00:31:16 · 个人记录

重点：保证有解。

对于某条可以选择的边 (u, v)，如果删去 u \to v 后不能再从 u 走到 v，则这条边必选；否则，选择 v \to u 仍然可以成环，选 v \to u 即可。

每次删边后暴力 dfs 即可。时间复杂度为 O(nm)。

可能需要注意重边的问题。

代码：

#include <stdio.h>

typedef struct {
    int nxt;
    int end;
} Edge;

int cnt = 0;
int a[5007], b[5007], t[5007], vis1[5007][5007], head[5007];
bool vis2[5007];
Edge edge[10007];

inline void add_edge(int start, int end){
    cnt++;
    edge[cnt].nxt = head[start];
    head[start] = cnt;
    edge[cnt].end = end;
}

void dfs(int u){
    vis2[u] = true;
    for (int i = head[u]; i != 0; i = edge[i].nxt){
        int x = edge[i].end;
        if (vis1[u][x] != 0 && !vis2[x]) dfs(x);
    }
}

int main(){
    int n, m;
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; i++){
        scanf("%d %d %d", &a[i], &b[i], &t[i]);
        vis1[a[i]][b[i]]++;
        add_edge(a[i], b[i]);
        if (t[i] == 0){
            vis1[b[i]][a[i]]++;
            add_edge(b[i], a[i]);
        }
    }
    for (int i = 1; i <= m; i++){
        if (t[i] == 1){
            printf("0\n");
        } else {
            vis1[a[i]][b[i]]--;
            for (int j = 1; j <= n; j++){
                vis2[j] = false;
            }
            dfs(a[i]);
            if (!vis2[b[i]]){
                vis1[a[i]][b[i]]++;
                vis1[b[i]][a[i]]--;
                printf("0\n");
            } else {
                printf("1\n");
            }
        }
    }
    return 0;
}