求一个图的最打的半联通子集=求一个图的最长链方案和个数
2022/8/30 23:53:03
本文主要是介绍求一个图的最打的半联通子集=求一个图的最长链方案和个数,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
拓扑图最长路 等于 背包问题求方案数
因为要求点不同 存在多条边同一情况 需要边判重(set)
拓扑求方案数
#include <iostream> #include <cstring> #include <algorithm> #include <unordered_set> using namespace std; typedef long long LL; const int N = 1e5+10,M=2e6+10; int n,m,mod; int h[N],hs[N], e[M], ne[M], idx;//hs表头2 int dfn[N],low[N],timestamp; int stk[N],top; bool in_stk[N]; int id[N],scc_cnt,Size[N]; int f[N],g[N];//f是点数 g方案数 void add(int h[],int a, int b) //给那个表头建立边 添加一条边a->b { e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ; } void tarjan(int u){ dfn[u]=low[u]=++timestamp; stk[++top]=u,in_stk[u]=true; for (int i = h[u]; ~i ; i =ne[i] ){ int j=e[i]; if(!dfn[j]){ tarjan(j); low[u]=min(low[u],low[j]); }else if(in_stk[j]){ low[u]=min(low[u],dfn[j]); } } if(dfn[u]==low[u]){ ++scc_cnt; int y; do{ y=stk[top--]; in_stk[y]=false; id[y]=scc_cnt; Size[scc_cnt]++; }while(u!=y); } } int main() { memset(h, -1, sizeof h); memset(hs, -1, sizeof hs); cin>>n>>m>>mod; while (m -- ){ int a,b; cin >> a>>b; add(h, a, b); } for (int i = 1; i <= n; i ++ ){ if(!dfn[i]) tarjan(i); } //这里需要建新图 unordered_set<LL>s;//(U,V) -> u*10000+v for(int i=1;i<=n;i++){ for (int j = h[i]; ~j ; j=ne[j]){ int k=e[j]; int a=id[i],b=id[k]; LL hash= a*1000000LL +b; if(a!=b && !s.count(hash)){//如果边之前没加过 add(hs,a, b);//加上这条边 s.insert(hash); } } } //scc 节点编号递减的顺序就是 top序 for (int i = scc_cnt; i ; i -- ){ if(!f[i]){//没有更新过就是起点 f[i]=Size[i]; g[i]=1; } for(int j=hs[i];~j;j=ne[j]){ int k=e[j]; if(f[k]<f[i]+Size[k]){ f[k]=f[i]+Size[k]; g[k]=g[i]; }else if(f[k]==f[i]+Size[k]){ g[k]=(g[k]+g[i])%mod; } } } int maxf=0,sum=0;//sum方案数 maxf最大值 for (int i = 1; i <= scc_cnt; i ++ ){ if(f[i]>maxf){ maxf=f[i]; sum=g[i]; } else if(f[i]==maxf) sum=(sum+g[i])%mod; } cout << maxf<<endl; cout << sum<<endl; return 0; }
这篇关于求一个图的最打的半联通子集=求一个图的最长链方案和个数的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?
- 2024-05-09企业src漏洞挖掘-有意思的命令执行