缩点九题

名字灵感来源于楼天城男人九题:joy:

Luogu2746 [USACO5.3]校园网Network of Schools

Link

题解

作为Tarjan入门题还是很不错的。

依据题意，可以把学校看成点，关系看成边，建图。显然，在同一个协议内的学校（点之间可以互相到达）我们可以看成一个点，这里就用到了Tarjan缩点。

由于缩点以后的图是不可能存在环的，因此只有可能有链。对于一条链，如果我们想从一个点到另外所有点，只需要找到那个入度为 $0$ 的点即可。

因此任务A就是缩点以后找到入度为 $0$ 的点。

对于任务B，需要加入协议的学校一定是入度为 $0$ 的点和出度为 $0$ 的点，在它们之间连一条边即可解决问题。当这两者的数量不相等时，就需要再找点配对。所以任务B的答案就是入度为 $0$ 的点和出度为 $0$ 的点的最大值。

Code

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

const int SIZE = 100 + 5;

int n, num, ind, tot;
int head[SIZE], low[SIZE], dfn[SIZE], in[SIZE], deg[SIZE], inDegree[SIZE];

std::stack < int > st;
std::set < int > G[SIZE];

struct node {
    int to, Next;
} edge[SIZE * SIZE];

inline int read()
{
    char ch = getchar();
    int f = 1, x = 0;
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + ch - '0'; ch = getchar(); }
    return x * f;
}

inline void Addedge(int x, int y)
{
    edge[++num].to = y;
    edge[num].Next = head[x];
    head[x] = num;
}

inline void DFS(int x)
{
    low[x] = dfn[x] = ++ind;
    st.push(x); in[x] = 1;
    for (int i = head[x]; i; i = edge[i].Next) {
        int v = edge[i].to;
        if (!dfn[v]) {
            DFS(v);
            low[x] = std::min(low[x], low[v]);
        }
        else if (in[v]) {
            low[x] = std::min(low[x], dfn[v]);
        }
    }
    if (dfn[x] == low[x]) {
        ++tot;
        while (st.top() != x) {
            deg[st.top()] = tot;
            in[st.top()] = 0;
            st.pop();
        }
        deg[st.top()] = tot;
        in[st.top()] = 0;
        st.pop();
    }
}

int main()
{
    int u, v;
    n = read();
    for (u = 1; u <= n; u++) {
        while (scanf("%d", &v) && v)
            Addedge(u, v);
    }
    for (int i = 1; i <= n; i++) {
        if (!dfn[i]) DFS(i);
    }
    for (u = 1; u <= n; u++) {
        for (int i = head[u]; i; i = edge[i].Next) {
            if (deg[edge[i].to] != deg[u] && G[deg[u]].find(deg[edge[i].to]) == G[deg[u]].end()) {
                G[deg[u]].insert(deg[edge[i].to]);
                inDegree[deg[edge[i].to]]++;
            }
        }
    }
    int ans1 = 0, ans2 = 0;
    for (int i = 1; i <= tot; i++) {
        if (!inDegree[i]) ans1++;
        if (!G[i].size()) ans2++;
    }
    if (tot == 1)
        printf("1\n0");
    else printf("%d\n%d\n", ans1, std::max(ans1, ans2));
    return 0;
}

Luogu2812 [USACO5.3]校园网Network of Schools（加强版）

吐槽

实在不晓得哪里加强了，上面的代码改一下数组大小就可以 $AC$

Luogu2341 [HAOI2006]受欢迎的牛|【模板】强连通分量

题解

不难发现，如果一些奶牛在一个连通块中，那么他们肯定互相喜欢，因此如果这个图都在一个强连通分量中，则不存在明星奶牛。根据这个分析，我们可以得出，如果一头奶牛是明星，那么它肯定是一个出度为 $1$ 入度为 $0$ 的点，如果有两个这样的点，那么他们两个肯定互相不喜欢，因此又不存在明星。

Code

有点Bug，建议不要对抄。

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

const int SIZE = 10000 + 5;
const int SIZE_EDGE = 50000 + 5;

int n, m, num, tot, ind;
int head[SIZE], in[SIZE], deg[SIZE], scc[SIZE], dfn[SIZE], low[SIZE], pail[SIZE];

std::stack < int > s;

struct node {
    int to, Next;
} edge[SIZE_EDGE];

inline int read()
{
    char ch = getchar();
    int f = 1, x = 0;
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + ch - '0'; ch = getchar(); }
    return x * f;
}

inline void Addedge(int x, int y)
{
    edge[++num].to = y;
    edge[num].Next = head[x];
    head[x] = num;
}

inline void DFS(int x)
{
    low[x] = dfn[x] = ++ind;
    in[x] = 1;
    s.push(x);
    for (int i = head[x]; i; i = edge[i].Next) {
        int v = edge[i].to;
        if (!dfn[v]) {
            DFS(v);
            low[x] = std::min(low[x], low[v]);
        }
        else if (in[v]) low[x] = std::min(low[x], dfn[v]);
    }
    if (low[x] == dfn[x]) {
        ++tot;
        while (s.top() != x) {
            in[s.top()] = 0;
            scc[s.top()] = tot;
            pail[tot]++;
            s.pop();
        }
        in[s.top()] = 0;
        scc[s.top()] = tot;
        pail[tot]++;
        s.pop();
    }
}

int main()
{
    int u, v;
    n = read(), m = read();
    for (int i = 1; i <= m; i++) {
        u = read(), v = read();
        Addedge(u, v);
    }
    for (int i = 1; i <= n; i++) {
        if (!dfn[v]) DFS(i);
    }
    for (u = 1; u <= n; u++) {
        for (int i = head[u]; i; i = edge[i].Next) {
            v = edge[i].to;
            if (scc[u] != scc[v]) deg[scc[u]]++;
        }
    }
    int flag = 0;
    for (int i = 1; i <= tot; i++) {
        if (!deg[i]) {
            if (flag) { puts("0"); return 0; }
            flag = i;
        }
    }
    printf("%d", pail[flag]);
    return 0;
}

Luogu2002 消息扩散

题解

这个题跟校园网那个第一个子任务差不多，只是需要判断一下自环，直接Tarjan缩点，记录入度为 $0$ 的点即可。

Code

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

const int SIZE = 100000 + 5;
const int SIZE_EDGE = 500000 + 5;

int n, m, num, top, ind, ans, point;
int head[SIZE], low[SIZE], dfn[SIZE], belong[SIZE], deg[SIZE], Stack[SIZE], in[SIZE];

struct node {
    int to, Next;
} edge[SIZE_EDGE];

inline int read()
{
    char ch = getchar();
    int f = 1, x = 0;
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = (x << 1) + (x <<  3) + ch - '0'; ch = getchar(); }
    return x * f;
}

inline void Addedge(int x, int y)
{
    edge[++num].to = y;
    edge[num].Next = head[x];
    head[x] = num;
}

inline void DFS(int x)
{
    low[x] = dfn[x] = ++ind;
    Stack[++top] = x, deg[x] = 1;
    for (int i = head[x]; i; i = edge[i].Next) {
        int v = edge[i].to;
        if (!dfn[v]) {
            DFS(v);
            low[x] = std::min(low[x], low[v]);
        }
        else if (deg[v]) low[x] = std::min(low[x], dfn[v]);
    }
    if (low[x] == dfn[x]) {
        ++point;
        int j = -1;
        while (j != x) {
            j = Stack[top--];
            belong[j] = point;
            deg[j] = 0;
        }
    }
}

int main()
{
    int u, v;
    n = read(), m = read();
    for (int i = 1; i <= m; i++) {
        u = read(), v = read();
        if (u != v) Addedge(u, v);
    }
    for (int i = 1; i <= n; i++) {
        if (!dfn[i]) DFS(i);
    }
    for (int k = 1; k <= n; k++) {
        for (int i = head[k]; i; i = edge[i].Next) {
            if (belong[k] != belong[edge[i].to])
                in[belong[edge[i].to]]++;
        }
    }
    for (int i = 1; i <= point; i++)
        if (!in[i]) ++ans;
    printf("%d\n", ans);
    return 0;
}

Luogu2169 正则表达式

题解

题面提示很明显了：

存在A到B的连接的同时也存在B到A的连接的话，那么A和B实际上处于同一局域网内，可以通过本地传输，这样花费的传输时间为0

意思就是告诉我们，在一个强连通分量的所有点距离都为 $0$ ，所以我们可以直接缩点，把这些在同一强连通分量中距离为 $0$ 的点看成一个点，中途重新建图，跑一遍SPFA求最短路即可。

Code

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

const int SIZE = 200000 + 5;
const int SIZE_EDGE = 1000000 + 5;
const int inf = 0x7f7f7f7f;

int n, m, num, tot;
int head[SIZE], dfn[SIZE], low[SIZE], deg[SIZE], in[SIZE], dis[SIZE], vis[SIZE];

std::stack < int > s;

struct node {
    int to, v, Next;
} edge[SIZE_EDGE];

inline int read()
{
    char ch = getchar();
    int f = 1, x = 0;
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + ch - '0'; ch = getchar(); }
    return x * f;
}

inline void Addedge(int x, int y, int z)
{
    edge[++num].to = y;
    edge[num].v = z;
    edge[num].Next = head[x];
    head[x] = num;
}

inline void DFS(int x)
{
    low[x] = dfn[x] = ++tot;
    in[x] = 1; s.push(x);
    for (int i = head[x]; i; i = edge[i].Next) {
        int v = edge[i].to;
        if (!dfn[v]) {
            DFS(v);
            low[x] = std::min(low[x], low[v]);
        }
        else if (in[v]) low[x] = std::min(low[x], dfn[v]);
    }
    if (dfn[x] == low[x]) {
        ++tot;
        while (s.top() != x) {
            deg[s.top()] = tot;
            in[s.top()] = 0;
            s.pop();
        }
        deg[s.top()] = tot;
        in[s.top()] = 0;
        s.pop();
    }
}

inline void SPFA()
{
    queue < int > Q;
    memset(dis, inf, sizeof(dis));
    dis[1] = 0, vis[1] = 1;
    Q.push(1);
    while (!Q.empty()) {
        int u = Q.front(), v, d;
        vis[u] = 0;
        Q.pop();
        for (int i = head[u]; i; i = edge[i].Next) {
            v = edge[i].to, d = edge[i].v;
            if (deg[u] == deg[v]) d = 0;
            if (dis[v] > dis[u] + d) {
                dis[v] = dis[u] + d;
                if (!vis[v]) {
                    vis[v] = 1;
                    Q.push(v);
                }
            }
        }
    }
}

int main()
{
    int u, v, d;
    n = read(), m = read();
    for (int i = 1; i <= m; i++) {
        u = read(), v = read(), d = read();
        Addedge(u, v, d);
    }
    for (int i = 1; i <= n; i++) {
        if (!dfn[i]) DFS(i);
    }
    SPFA();
    printf("%d\n", dis[n]);
    return 0;
}

Luogu2194 HXY烧情侣

题解

这道题有一次CJ模拟赛中好像出了一个类似的，当时没切(~~TCL~~)。

首先HXY一次性能走一遍的电影院是一个强连通分量，可以先缩一下点。

之后可以发现，我们只要烧完所有的联通块就可以了。因为烧一个连通块的最小代价就是那一个连通块中最小的点权，所以总共最小的代价就是每一个联通块中最小点权之和。

至于方案数，根据乘法原理，只要记录每个联通块中最小点权的个数最后算乘积即可。

Code

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

const int SIZE = 100000 + 5;
const int SIZE_EDGE = 300000 + 5;
const int Mod = 1e9 + 7;

int n, m, num, tot, ind;
int head[SIZE], low[SIZE], dfn[SIZE], a[SIZE], in[SIZE], scc[SIZE];

std::stack < int > s;
std::vector < int > g[SIZE];

struct node {
    int to, Next;
} edge[SIZE_EDGE];

inline int read()
{
    char ch = getchar();
    int f = 1, x = 0;
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + ch - '0'; ch = getchar(); }
    return x * f;
}

inline void Addedge(int x, int y)
{
    edge[++num].to = y;
    edge[num].Next = head[x];
    head[x] = num;
}

inline void DFS(int x)
{
    low[x] = dfn[x] = ++ind;
    in[x] = 1; s.push(x);
    for (int i = head[x]; i; i = edge[i].Next) {
        int v = edge[i].to;
        if (!dfn[v]) {
            DFS(v);
            low[x] = std::min(low[x], low[v]);
        }
        else if (in[v])
            low[x] = std::min(low[x], dfn[v]);
    }
    if (low[x] == dfn[x]) {
        ++tot;
        while (s.top() != x) {
            scc[s.top()] = tot;
            in[s.top()] = 0;
            g[tot].push_back(s.top());
            s.pop();
        }
        scc[s.top()] = tot;
        in[s.top()] = 0;
        g[tot].push_back(s.top());
        s.pop();
    }
}

int main()
{
    n = read();
    for (int i = 1; i <= n; i++) a[i] = read();
    m = read();
    int u, v;
    for (int i = 1; i <= m; i++) {
        u = read(), v = read();
        Addedge(u, v);
    }
    for (int i = 1; i <= n; i++) {
        if (!dfn[i]) DFS(i);
    }
    // std::cout << tot << endl;
    int ans1 = 0, ans2 = 1;
    for (int i = 1; i <= tot; i++) {
        int cnt = 0, Min = Mod;
        for (int j = 0; j < g[i].size(); j++) {
            if (a[g[i][j]] < Min) {
                Min = a[g[i][j]];
                cnt = 1;
            }
            else if (Min == a[g[i][j]]) ++cnt;
        }
        ans1 += Min;
        ans2 = (ans2 % Mod * cnt % Mod) % Mod;
    }
    printf("%d %d\n", ans1, ans2);
    return 0;
}

Luogu2656 采蘑菇

题解

很显然，一条路径如果是一个环，我们便可以不停地走，直到取完这个环中所有的蘑菇为止。

因此我们先Tarjan缩点找环，因为我们希望取得蘑菇越多越好，所以我们缩点后跑一遍最长路，便可以解决。

Code

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

const int SIZE = 80000 + 5;
const int SIZE_EDGE = 200000 + 5;

int n, m, s, num1, num2, tot, ind;
int head1[SIZE], head2[SIZE], low[SIZE], dfn[SIZE], in[SIZE], scc[SIZE], w[SIZE], dis[SIZE], vis[SIZE];
double coe[SIZE_EDGE];

std::stack < int > st;

struct node {
    int from, to, v, Next;
} edge1[SIZE_EDGE], edge2[SIZE_EDGE];

inline int read()
{
    char ch = getchar();
    int f = 1, x = 0;
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + ch - '0'; ch = getchar(); }
    return x * f;
}

inline void Addedge1(int x, int y, int z)
{
    edge1[++num1].to = y;
    edge1[num1].from = x;
    edge1[num1].v = z;
    edge1[num1].Next = head1[x];
    head1[x] = num1;
}

inline void Addedge2(int x, int y, int z)
{
    edge2[++num2].to = y;
    edge2[num2].from = x;
    edge2[num2].v = z;
    edge2[num2].Next = head2[x];
    head2[x] = num2;
}

inline void DFS(int x)
{
    low[x] = dfn[x] = ++ind;
    in[x] = 1; st.push(x);
    for (int i = head1[x]; i; i = edge1[i].Next) {
        int v = edge1[i].to;
        if (!dfn[v]) {
            DFS(v);
            low[x] = std::min(low[x], low[v]);
        }
        else if (in[v]) low[x] = std::min(low[x], dfn[v]);
    }
    if (low[x] == dfn[x]) {
        ++tot;
        while (st.top() != x) {
            scc[st.top()] = tot;
            in[st.top()] = 0;
            st.pop();
        }
        scc[st.top()] = tot;
        in[st.top()] = 0;
        st.pop();
    }
}

inline void SPFA()
{
    queue < int > Q;
    memset(dis, -1, sizeof(dis));
    dis[s] = w[s], vis[s] = 1;
    Q.push(s);
    while (!Q.empty()) {
        int u = Q.front(), v;
        Q.pop();
        vis[u] = 0;
        for (int i = head2[u]; i; i = edge2[i].Next) {
            v = edge2[i].to;
            if (dis[v] < dis[u] + edge2[i].v + w[v]) {
                dis[v] = dis[u] + edge2[i].v + w[v];
                if (!vis[v]) {
                    vis[v] = 1;
                    Q.push(v);
                }
            }
        }
    }
}

int main()
{
    int u, v, d;
    n = read(), m = read();
    for (int i = 1; i <= m; i++) {
        u = read(), v = read(), d = read(); scanf("%lf", &coe[i]);
        Addedge1(u, v, d);
    }
    for (int i = 1; i <= n; i++) {
        if (!dfn[i]) DFS(i);
    }
    for (int i = 1; i <= m; i++) {
        u = edge1[i].from, v = edge1[i].to;
        if (scc[u] == scc[v]) {
            int id = scc[v];
            d = edge1[i].v;
            while (d) {
                w[id] += d;
                d = (int) d * coe[i];
            }
        }
        else Addedge2(scc[u], scc[v], edge1[i].v);
    }
    s = read(), s = scc[s];
    // for (int i = 1; i <= m; i++) printf("%d ", scc[i]);
    SPFA();
    int ans = 0;
    for (int i = 1; i <= n; i++)
        ans = std::max(ans, dis[i]);
    printf("%d\n", ans);
    return 0;
}

Luogu1407 [国家集训队]稳定婚姻

题解

这道题的题面对于广大单纯的中学生还是有点难理解的。

把所有交往过的男女连线，会发现出现了环。那么在环里的男女就是不稳定婚姻（暗示马蓉王宝强）

所以想到可以使用Tarjan找环。

然而Tarjan是适用于有向图的，这是个无向图。

然后就不会做了，题解说男女交替连边建图可以跑，那我就照做了。

详情看代码。

Code

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

const int SIZE = 8000 + 5;
const int SIZE_EDGE = 20000 + 5;

int n, m, ind, tot, num;
int head[SIZE], low[SIZE], dfn[SIZE], in[SIZE], scc[SIZE];

std::map < string, int > M;
std::stack < int > s;

struct node {
    int to, Next;
} edge[SIZE_EDGE * 5];

inline int read()
{
    char ch = getchar();
    int f = 1, x = 0;
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + ch - '0'; ch = getchar(); }
    return x * f;
}

inline void Addedge(int x, int y)
{
    edge[++num].to = y;
    edge[num].Next = head[x];
    head[x] = num;
}

inline void DFS(int x)
{
    low[x] = dfn[x] = ++ind;
    in[x] = 1; s.push(x);
    for (int i = head[x]; i; i = edge[i].Next) {
        int v = edge[i].to;
        if (!dfn[v]) {
            DFS(v);
            low[x] = std::min(low[x], low[v]);
        }
        else if (in[v]) low[x] = std::min(low[x], dfn[v]);
    }
    if (low[x] == dfn[x]) {
        ++tot;
        while (s.top() != x) {
            scc[s.top()] = tot;
            in[s.top()] = 0;
            s.pop();
        }
        scc[s.top()] = tot;
        in[s.top()] = 0;
        s.pop();
    }
}

int main()
{
    string Boy, Girl;
    n = read();
    for (int i = 1; i <= n; i++) {
        std::cin >> Girl >> Boy;
        M[Girl] = i;
        M[Boy] = i + n;
        Addedge(i, i + n);
    }
    m = read();
    for (int i = 1; i <= m; i++) {
        std::cin >> Girl >> Boy;
        Addedge(M[Boy], M[Girl]);
    }
    for (int i = 1; i <= n << 1; i++) {
        if (!dfn[i]) DFS(i);
    }
    for (int i = 1; i <= n; i++) {
        if (scc[i] == scc[i + n]) puts("Unsafe");
        else puts("Safe");
    }
    return 0;
}

Luogu2746 [USACO5.3]校园网Network of Schools

题解

Code

Luogu2812 [USACO5.3]校园网Network of Schools（加强版）

吐槽

Luogu2341 [HAOI2006]受欢迎的牛|【模板】强连通分量

题解

Code

Luogu2002 消息扩散

题解

Code

Luogu2169 正则表达式

题解

Code

Luogu2194 HXY烧情侣

题解

Code

Luogu2656 采蘑菇

题解

Code

Luogu1407 [国家集训队]稳定婚姻

题解

Code

Luogu4767 [IOI2000]邮局

ZJOI2018第二式游记

Tony102

Comments | 1 条评论

博主 BigYellowDog

取消回复