链接:

http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1006&cid=872

题意:

Z 国近年来一直在考虑遏制国土沙漠化的方案。在 Z 国广阔的疆域上，有着许多的沙漠。沙漠上干旱少雨，荒无人烟，仅有仙人掌能在这种魔鬼环境中生存。经过 Z 国地质探测局的调查，他们得到了沙漠的实地情况。Z 国的地质探测局是一个热爱 CCPC 的机构，他们喜欢使用图论的方式来描述看到的景色。在得到的数据中，沙漠中的每一个连通块都是一棵仙人掌；一个连通块是一棵仙人掌当且仅当连通块中不存在重边和自环，并且每一条边仅被至多一个简单环覆盖。

经过一番评估，Z 国决定通过删去沙漠中的一些边，最终将沙漠变为森林。这里我们定义森林满足：森林中每一个连通块都是一棵树，而树是边数等于点数减一的连通块。现在给定一个包含 n 个点的沙漠，请你求出 Z 国一共有多少种满足要求的沙漠改造方案。两种方案不同当且仅当方案中被删去的边集不同。由于答案可能很大，请将最终答案对 998244353 取模后输出。

思路:

Dfs判断环, sum为除了环剩下的边, 答案为2^n乘以每个环的次数, m个边的环的次数为2^m-1.

代码:

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int MAXN = 3e5+10;

const LL MOD = 998244353;

vector<int> G[MAXN];

int Deg[MAXN], Cyc[MAXN], Vis[MAXN];

int n, m, cnt;

LL QucikMi(LL a, int b)

{

    LL res = 1;

    while (b)

    {

        if (b&1)

            res = (res*a)%MOD;

        a = (a*a)%MOD;

        b >>= 1;

    }

    return res;

}

void Dfs(int x, int fa)

{

    Deg[x] = Deg[fa]+1;

    Vis[x] = 1;

    for (int i = 0;i < G[x].size();i++)

    {

        int node = G[x][i];

        if (node == fa)

            continue;

        if (Deg[node] != 0)

        {

            if (Deg[x] > Deg[node])

                Cyc[++cnt] = Deg[x]-Deg[node]+1;

        }

        else

            Dfs(node, x);

    }

}

int main()

{

//    freopen("test.in", "r", stdin);

    cnt = 0;

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

    int u, v;

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

    {

        scanf("%d%d", &u, &v);

        G[u].push_back(v);

        G[v].push_back(u);

    }

    Dfs(1, 0);

    int sum = m;

    for (int i = 1; i <= cnt; i++)

        sum -= Cyc[i];

    LL ans = QucikMi(2LL, sum);

    for (int i = 1; i <= cnt; i++)

    {

        LL tmp = QucikMi(2LL, Cyc[i]);

        tmp = (tmp - 1 + MOD) % MOD;

        ans = (ans * tmp) % MOD;

    }

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

    return 0;

}

/*

 */

巴特西

2019CCPC秦皇岛赛区（重现赛）- F

链接:

题意:

思路:

代码:

最新文章

热门文章