noip模拟赛黑骑士

题目描述
江爷爷给你出了一道题：
给你一个图，保证每个点最多属于一个简单环，每个点度数最多为3，求这个图有多少“眼镜图形个数”
保证图联通哦~
其中“眼镜图形个数”，定义为三元组(x,y,S)，其中x和y表示图上的两个点，S表示一条x到y的简单路径，而且必
须满足：
1.x和y分别在两个不同的简单环上
2.x所在的简单环与路径S的所有交点仅有x，y所在的简单环与路径S的所有交点仅有y。
(x,y,S)与(y,x,S)算同一个眼镜
如果你无法理解，可以参考样例。
保证图是联通的
输入输出格式
输入格式：
第一行两个数n和m
之后m行，每行两个数x，y表示x和y之间有一条边。
输出格式：
输出一个数，表示眼镜的个数对19260817取膜的结果
输入输出样例
输入样例#1：
说明
样例#3，#4，#5，#6见下发的文件
非常抱歉，出了点小锅，sample5.out好像是空文件，应该是6734568
【子任务】
11 12
1 2
2 3
3 4
4 5
5 1
4 6
6 7
7 8
8 9
9 10
10 11
11 7
输出样例#1：
1
输入样例#2：
14 16
1 2
2 3
3 4
4 1
3 5
5 6
6 7
7 8
8 9
9 6
9 13
13 14
13 10
10 11
11 12
12 10
输出样例#2：
4
子任务会给出部分测试数据的特点。
如果你在解决题目中遇到了困难, 可以尝试只解决一部分测试数据。
测试点编号　　n的范围　　　　m的范围　　　　　特殊性质
测试点1 n <= 10 m <= 20
测试点2 n <= 20 m <= 40
测试点3 n <= 20 m <= 40
测试点4 n <= 2000 m <= 4000
测试点5 n <= 2000 m <= 4000
测试点6 n <= 1000000 m <= 2000000 简单环个数 <= 2000
测试点7 n <= 1000000 m <= 2000000 简单环个数 <= 2000
测试点8 n <= 1000000 m <= 2000000
测试点9 n <= 1000000 m <= 2000000
测试点10 n <= 1000000 m <= 2000000

分析：有环在是不好处理的，先把所有环给缩成一个点.观察样例可以发现，如果环与环中间还有x个环，那么实际上这两个点可以构成2^x个眼镜，因为中间的每个环既可以走上面也可以走下面.于是dfs缩点似乎可以拿70分.

其实一个眼镜中间的圆点可以看做根节点，两个镜框可以看做是树，那么我们可以以1号点为根节点来建一棵树来进行树形dp.记录的状态不能是以i为根的子树的眼镜数，因为这样不好转移，应该将状态定义为半眼镜数.对于环和圆点要分别讨论，每个环可以看做是两条路径，所以在统计答案或者更新f的时候都要*2,因为每个子树是独立的，最后要把它们合并到一起，这里利用乘法原理来解决.可以得到f[x] = Σf[son[x]],if x为环 then f[x] = f[x] * 2 + 1,因为子树的可以走两个方向，自己也可以当做一个半眼镜的端点，合并子树的时候ans += f[x] * f[son[x]],if x是环 then ans += f[x] * f[son[x]].因为f[x]随着子节点的处理越来越大，所以答案不会遗漏.

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

const int maxn = , maxm = , mod = ;

int n, m, head[maxn], nextt[maxm], to[maxm], tot = , cnt, fa[maxn], scc[maxn], limit;

int head2[maxn], to2[maxm], nextt2[maxm], tot2 = ;

bool vis[maxn];

long long ans, f[maxn];

void add(int x, int y)

{

    to[tot] = y;

    nextt[tot] = head[x];

    head[x] = tot++;

}

void add2(int x, int y)

{

    to2[tot2] = y;

    nextt2[tot2] = head2[x];

    head2[x] = tot2++;

}

void find(int x, int y)

{

    scc[x] = cnt;

    if (x == y)

        return;

    find(fa[x], y);

}

void dfs(int u)

{

    vis[u] = ;

    for (int i = head[u]; i; i = nextt[i])

    {

        int v = to[i];

        if (v == fa[u] || scc[v])

            continue;

        if (vis[v])

        {

            cnt++;

            find(u, v);

        }

        else

        {

            fa[v] = u;

            dfs(v);

        }

    }

}

void build(int u)

{

    vis[u] = ;

    for (int i = head[u]; i; i = nextt[i])

    {

        int v = to[i];

        if (v == fa[u] || vis[v])

            continue;

        if (scc[u] != scc[v])

        {

            add2(scc[u], scc[v]);

            add2(scc[v], scc[u]);

        }

        build(v);

    }

}

void solve(int u, int from)

{

    f[u] = ;

    for (int i = head2[u]; i; i = nextt2[i])

    {

        int v = to2[i];

        if (v == from)

            continue;

        solve(v, u);

        long long temp = f[u] * f[v] % mod;

        if (u <= limit)

            temp *= ;

        ans = (ans + temp) % mod;

        f[u] = (f[u] + f[v]) % mod;

    }

    if (u <= limit)

    {

        ans = (ans + f[u]) % mod;

        f[u] = (f[u] *  + ) % mod;

    }

}

int main()

{

    scanf("%d%d", &n, &m);

    for (int i = ; i <= m; i++)

    {

        int x, y;

        scanf("%d%d", &x, &y);

        add(x, y);

        add(y, x);

    }

    dfs();

    limit = cnt;

    for (int i = ; i <= n; i++)

        if (!scc[i])

            scc[i] = ++cnt;

    memset(vis, , sizeof(vis));

    build();

    solve(, );

    printf("%lld\n", ans);

    return ;

}

巴特西

noip模拟赛黑骑士

最新文章

热门文章

巴特西

noip模拟赛 黑骑士

最新文章

热门文章

noip模拟赛黑骑士