Forest Program 2019CCPC秦皇岛F 2019-05-28 算法竞赛 暂无评论 69 次阅读 # Forest Program 2019CCPC秦皇岛F (hdu重现赛） 题目链接：[http://acm.hdu.edu.cn/showproblem.php?pid=6736](http://acm.hdu.edu.cn/showproblem.php?pid=6736)  ## 题意 一个 n 个节点 m 条边的无向图，没有重边和自环，每条边被至多一个简单环覆盖，要求去掉一些边使剩余的连通部分都为树（即使图成为森林），问有多少种方案。 ## 思路 每条边都有去掉和不去掉两个状态，但剩余部分不能有环 设成环的边数分别为 c1 , c2 , c3 ...ck 不成环的边数为 b 答案 ans = $2^{b}$ \* $\prod_ {i=1} ^ {k}$ ($2^{ci}-1$) 用 dfs 暴力一下每个环的边数，book[] 存的是到达每个节点的步数，book[1]=1, 从1开始dfs; 设当前为节点i , 和 i 连接的下一个节点为 j ，若 book [ j ] >0&&book [ j ] < book [ i ], 即有一个环。 ## 代码 ```javascript #include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=3e5+10; const int mod=998244353; int n,m; int head[N]; vector<int> v[N]; vector<int> cnt; int book[N]; void dfs(int p,int num) { book[p]=num; for(int i=0; i<v[p].size(); i++) { if(book[v[p][i]]<num&&book[v[p][i]]>0&&num-book[v[p][i]]>1) { cnt.push_back(num-book[v[p][i]] +1) ; } else if(book[v[p][i]]==0) { dfs(v[p][i],num+1); } } } ll quick_pow(ll x,ll n) { ll res=1; while(n>0) { if(n&1) res=(res%mod*x%mod)%mod; x=x*x%mod; n>>=1; } return res; } int main() { std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); while(cin>>n>>m) { int l,r; for(int i=1; i<=n; i++) v[i].clear(); for(int i=1; i<=m; i++) { cin>>l>>r; v[l].push_back(r); v[r].push_back(l); } memset(book,0,sizeof(book)); cnt.clear(); dfs(1,1); ll sum=0,ans=1; for(int i=0; i<cnt.size(); i++) { sum+=cnt[i]; ans=(ans*(quick_pow(2,cnt[i])-1))%mod; } ans=(ans*quick_pow(2,(ll)m-sum)%mod)%mod; cout<<ans<<endl; } } ``` 标签: 算法 本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可。
评论已关闭