CF555E Case of Computer Network

博主： tony102
发布时间：2021 年 09 月 24 日
1623 次浏览
1 条评论
919字数
分类：题解

[Link](https://www.luogu.com.cn/problem/CF555E)

[51nod 1470](https://www.51nod.com/Challenge/Problem.html#problemId=1470)

## Sol

不错的题目

拿到题目感觉没啥想法，但是仔细想想，会发现切入点应该是什么样的边如何影响有没有解。

假如有一个环，定向以后仍然环上的点仍然可以互相到达。那么环是我们可以不需要考虑合不合法的因素。推广一下，在一个 e-DDC 中的点给边定向以后也是都可以互相到达的。因此，可以先对原图进行 e-DDC 缩边，得到了一棵原图中桥组成的树。

现在影响是否有解的只有这棵树上的边了。相当于我们要给树边定向。我们钦定对于一个限制 $(s, t)$，$p$ 为 $s,t$ 对应的 e-DDC 的树上结点的 LCA。从 $s \to p$ 的为正向，从 $v \to p$ 的为反向。那么可以把 $s \to p$ 的路径上的点全部 $+1$，$t \to p$ 的全部 $-1$。只需要检查有没有一个点的权值为 $0$ 即可。

如果你想多一个 $\log$，可以选择线段树。但是只需要树上差分就行了。

## Code

```cpp
#include <bits/stdc++.h>
using namespace std;

typedef vector < int > vec;
const int SIZE = 5e5 + 5;

int n, m, q, num = 1, tim, cnt, N;
int head[SIZE], dfn[SIZE], low[SIZE], bri[SIZE], deg[SIZE], col[SIZE];
int dep[SIZE], idx[SIZE], bel[SIZE], fa[SIZE], siz[SIZE], son[SIZE], dif1[SIZE], dif2[SIZE];

struct node {
    int to, nxt;
} edge[SIZE << 1];
vec g[SIZE];

namespace GTR {
	const int bufl = 1 << 15;
	char buf[bufl], *s = buf, *t = buf;
	inline int fetch() {
		if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
		return *s++;
	}
	inline int read() {
		int a = 0, b = 1, c = fetch();
		while (c < 48 || c > 57) b ^= c == '-', c = fetch();
		while (c >= 48 && c <= 57) a = (a << 1) + (a << 3) + c - 48, c = fetch();
		return b ? a : -a;
	}
} using GTR::read;

void addEdge(int u, int v) {
    edge[++ num] = (node) {v, head[u]}, head[u] = num;
}

void dfs(int u, int p) {
    dfn[u] = low[u] = ++ tim;
    for (int i = head[u], v; i; i = edge[i].nxt) {
        v = edge[i].to;
        if (!dfn[v]) {
            dfs(v, i);
            low[u] = std::min(low[u], low[v]);
            if (low[v] > dfn[u]) bri[i] = bri[i ^ 1] = 1;
        }
        else if (i != (p ^ 1)) low[u] = std::min(low[u], dfn[v]);
    }
}

void ddc(int u) {
    col[u] = cnt;
    for (int i = head[u], v; i; i = edge[i].nxt) {
        v = edge[i].to;
        if (col[v] || bri[i]) continue;
        ddc(v);
    }
}

void dfs0(int u, int anc) {
    siz[u] = 1, idx[u] = N;
    for (int v: g[u]) {
        if (v == anc) continue;
        fa[v] = u, dep[v] = dep[u] + 1; dfs0(v, u); siz[u] += siz[v];
        if (siz[son[u]] < siz[v]) son[u] = v;
    }
}

void dfs1(int u, int top) {
    bel[u] = top;
    if (son[u]) dfs1(son[u], top);
    for (int v: g[u]) {
        if (v == son[u] || v == fa[u]) continue;
        dfs1(v, v);
    }
}

int lca(int u, int v) {
    while (bel[u] ^ bel[v]) {
        if (dep[bel[u]] < dep[bel[v]]) std::swap(u, v);
        u = fa[bel[u]];
    }
    return dep[u] < dep[v] ? u : v;
}

int judge(int u) {
    for (int v: g[u]) {
        if (v == fa[u]) continue;
        if (!judge(v) || (dif1[v] && dif2[v])) return 0;
        dif1[u] += dif1[v], dif2[u] += dif2[v];
    }
    return 1;
}

int main() {
    // freopen("code.in", "r", stdin);
    n = read(), m = read(), q = read();
    for (int i = 1, u, v; i <= m; ++ i) {
        u = read(), v = read();
        addEdge(u, v), addEdge(v, u);
    }
    for (int i = 1; i <= n; ++ i)
        if (!dfn[i]) dfs(i, 0);
    for (int i = 1; i <= n; ++ i) {
        if (!col[i]) { ++ cnt; ddc(i); }
    }
    for (int u = 1; u <= n; ++ u) {
        for (int i = head[u], v; i; i = edge[i].nxt) {
            v = edge[i].to;
            if (col[u] < col[v]) {
                g[col[u]].emplace_back(col[v]), 
                g[col[v]].emplace_back(col[u]);
            }
        }
    }
    for (int i = 1; i <= cnt; ++ i) {
        if (!idx[i]) {
            dep[i] = 0, fa[i] = 0, idx[i] = ++ N;
            dfs0(i, 0), dfs1(i, 1);
        }
    }
    for (int i = 1, u, v; i <= q; ++ i) {
        u = col[read()], v = col[read()];
        if (u == v) continue;
        if (idx[u] != idx[v]) return puts("No"), 0;
        int par = lca(u, v);
        -- dif1[par], -- dif2[par]; ++ dif1[u], ++ dif2[v];
    }
    for (int i = 1; i <= cnt; ++ i) {
        if (dep[i] == 0 && !judge(i)) return puts("No"), 0;
    }
    puts("Yes");
    return 0;
}
```

最后修改：2021 年 09 月 24 日

如果觉得我的文章对你有用，请随意赞赏

1 条评论

abcyz
September 28th, 2021 at 08:26 pm

再次膜拜托老师

回复

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

rlenitkthe
真好呢
暴力膜托
暴力膜托暴力膜托暴力膜托暴力膜托暴力膜托暴力膜托暴力膜托%%%
TosakaUCW
前排狂暴膜托！
菲兹克斯喵
竟然……又找到一个校友……而且初中和高中都是同一个学校……天哪...
暴力膜托
快给黄明珍开个方子吧，可怜孩子补太猛了

CF555E Case of Computer Network

tony102 • 2021 年 09 月 24 日

[Link](https://www.luogu.com.cn/problem/CF555E)

[51nod 1470](https://www.51nod.com/Challenge/Problem.html#problemId=1470)

## Sol

不错的题目

拿到题目感觉没啥想法，但是仔细想想，会发现切入点应该是什么样的边如何影响有没有解。

如果你想多一个 $\log$，可以选择线段树。但是只需要树上差分就行了。

## Code

```cpp
#include <bits/stdc++.h>
using namespace std;

typedef vector < int > vec;
const int SIZE = 5e5 + 5;

int n, m, q, num = 1, tim, cnt, N;
int head[SIZE], dfn[SIZE], low[SIZE], bri[SIZE], deg[SIZE], col[SIZE];
int dep[SIZE], idx[SIZE], bel[SIZE], fa[SIZE], siz[SIZE], son[SIZE], dif1[SIZE], dif2[SIZE];

struct node {
    int to, nxt;
} edge[SIZE << 1];
vec g[SIZE];

void addEdge(int u, int v) {
    edge[++ num] = (node) {v, head[u]}, head[u] = num;
}

void ddc(int u) {
    col[u] = cnt;
    for (int i = head[u], v; i; i = edge[i].nxt) {
        v = edge[i].to;
        if (col[v] || bri[i]) continue;
        ddc(v);
    }
}

void dfs1(int u, int top) {
    bel[u] = top;
    if (son[u]) dfs1(son[u], top);
    for (int v: g[u]) {
        if (v == son[u] || v == fa[u]) continue;
        dfs1(v, v);
    }
}

int lca(int u, int v) {
    while (bel[u] ^ bel[v]) {
        if (dep[bel[u]] < dep[bel[v]]) std::swap(u, v);
        u = fa[bel[u]];
    }
    return dep[u] < dep[v] ? u : v;
}

CF555E Case of Computer Network

1 条评论

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

名人传

VP: AtCoder Beginner Contest 222(ABC222)

写在 CSP-S2021 前

机房标准化岚语发音对照

VP: AtCoder Beginner Contest 221(ABC221)

CF616E Sum of Remainders

CF101D Castle

Luogu4173 残缺的字符串

CF1437D Minimal Height Tree

跟不同的人聊天的收获

CF555E Case of Computer Network

1 条评论

发表评论 取消回复 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

CF555E Case of Computer Network

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款