WA31,求助
查看原帖
WA31,求助
104241
piuke楼主2020/8/20 15:56

RT

#define MAXN 300005
#define MAXM 300005
const int mod = 1e9 + 7;
int n, m;
struct edge {
    int v, nxt, w;
} e[MAXM << 1];
int f[MAXN], tot = 1;
inline void addEdge(int u, int v, int w) { tot++, e[tot].v = v, e[tot].nxt = f[u], e[tot].w = w, f[u] = tot; }
int low[MAXN], dfn[MAXN], idx;
int bel[MAXN], siz[MAXN], sum;
bool isc[MAXM << 1];
inline void dfs(int x, int fa) {
    dfn[x] = low[x] = ++idx;
    for(int i = f[x]; i; i = e[i].nxt) {
        int v = e[i].v;
        if(!dfn[v]) {
            dfs(v, x);
            if(low[v] > dfn[x])
                isc[i] = isc[i ^ 1] = 1;
            low[x] = Min(low[x], low[v]);
        }
        else if(dfn[x] > dfn[v] && v != fa)
            low[x] = Min(low[x], dfn[v]);
    }
}
int w[MAXN];//缩点后每个点点权
int cnt;
inline void ddfs(int x) {
    bel[x] = cnt;
    for(int i = f[x]; i; i = e[i].nxt) {
        int v = e[i].v;
        if(isc[i]) continue;
        if(bel[v]) continue;
        w[cnt] |= e[i].w;
        ddfs(v);
    }
}
int st, fin;
vector<pii>G[MAXN];
inline void dddfs(int x, int fa, int way) {
    way |= w[x];
    if(x == fin) {
        if(way) exit(puts("YES") & 0);
        exit(puts("NO") & 0);  
    }
    for(auto v : G[x]) {
        if(v.first == fa) continue;
        dddfs(v.first, x, way | v.second);
    }
}
signed main() {
    read(n, m);
    for(int i = 1; i <= m; i++) {
        int u, v, w; read(u, v, w);
        addEdge(u, v, w); addEdge(v, u, w);
    }
    for(int i = 1; i <= n; i++)
        if(!dfn[i])
            dfs(i, -1);
    for(int i = 1; i <= n; i++)
        if(!bel[i]) {
            cnt++;
            ddfs(i);
        }
    for(int i = 1; i <= n; i++) {
        for(int j = f[i]; j; j = e[j].nxt) {
            int x = bel[i], y = bel[e[j].v];
            if(x == y) continue;
            G[x].push_back(make_pair(y, e[j].w));
        }
    }
    read(st, fin); st = bel[st], fin = bel[fin];
    dddfs(st, -1, 0);
}
2020/8/20 15:56
加载中...