题解 竞赛图
2021/8/15 6:35:42
本文主要是介绍题解 竞赛图,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
传送门
考试的时候想到了一个应该有60pts的 \(O(2^nn^2T)\) 但是 \(n^2\) 只是枚举边的状压
然后挂成40pts,从中午12点拍到晚上5点半没拍出来
记得哪天去要下这题数据
考试的时候如何发现这些奇奇怪怪的性质啊……
正解需要 \(O(2^nT)\) 才能过
所以枚举点集跑check一定会炸,考虑可行性DP
尤其注意本题的图两点之间一定有边,且一定只指向一个方向
发现对于一个强联通的诱导子图S,必然存在且仅存在一个强连通的子图T,满足T内的点到S-T中所有点的边都是从T到S-T的
那么发现这个玩意有可扩展性
对于一个强连通分量,令其出边集合为R,那么S与R的子集的并一定不合法
那么问题转化为 \(O(2^n)\) 预处理出所有出边集合
想了半天没想到,但其实很简单
注意要特判一下 \(i=lowbit(i)\) ,也即 \(i\) 中只有一位的情况,或直接将 \(reach_0\) 置为全1
Code:
#include <bits/stdc++.h> using namespace std; #define INF 0x3f3f3f3f #define N 25 #define ll long long #define reg register int #define min(a, b) ((a)<(b)?(a):(b)) //#define int long long char buf[1<<21], *p1=buf, *p2=buf; #define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf, 1, 1<<21, stdin)), p1==p2?EOF:*p1++) inline int read() { int ans=0, f=1; char c=getchar(); while (!isdigit(c)) {if (c=='-') f=-f; c=getchar();} while (isdigit(c)) {ans=(ans<<3)+(ans<<1)+(c^48); c=getchar();} return ans*f; } int n; bool mp[N][N]; int head[N], size; struct edge{int to, next;}e[N*N*2]; inline void add(int s, int t) {e[++size].to=t; e[size].next=head[s]; head[s]=size;} namespace force{ int vis, s; void dfs(int u) { vis|=1<<u; for (reg i=0; i<n; ++i) if (mp[u][i] && s&(1<<i) && !(vis&(1<<i))) dfs(i); } void solve() { int lim=1<<n, ans=0; for (s=0; s<lim; ++s) { for (reg i=0; i<n; ++i) if (s&(1<<i)) { vis=0; dfs(i); if (vis!=s) goto jump; } ++ans; jump: ; } printf("%d\n", ans); } } namespace task1{ int vis, s, tot; int dfn[N], low[N]; bool tarjan(int u) { //if (s==(1<<n)-1) cout<<"tarjan "<<u<<endl; vis|=1<<u; dfn[u]=low[u]=++tot; bool flag=0; //for (reg i=0; i<n; ++i) // if (mp[u][i] && s&(1<<i)) { for (int t=head[u],i; ~t; t=e[t].next) { i = e[t].to; if (!(s&(1<<i))) continue; flag=1; //cout<<"visit: "<<i<<endl; if (!(vis&(1<<i))) { if (!tarjan(i)) return 0; if (low[i]>dfn[u]) return 0; low[u]=min(low[u], low[i]); } else low[u]=min(low[u], low[i]); //, cout<<dfn[i]<<endl; } //if (s==(1<<n)-1) cout<<"tarjan "<<u<<" return "<<flag<<' '<<low[u]<<endl; return flag; } void solve() { int lim=1<<n, ans=1; for (s=1; s<lim; ++s) { //memset(dfn, 0, sizeof(int)*n); //memset(low, 0, sizeof(int)*n); vis=tot=0; for (reg i=0; i<n; ++i) if (s&(1<<i)) { //if (tarjan(i)) cout<<bitset<3>(s)<<' '<<bitset<3>(vis)<<' '<<i<<endl; if (tarjan(i) && vis==s) { ++ans; //cout<<bitset<5>(s)<<endl; } break; } } printf("%d\n", ans+n); } } namespace task{ int to[1<<24]; bool vis[1<<24]; void solve() { memset(to, 0, sizeof(to)); memset(vis, 0, sizeof(vis)); int lim=1<<n, ans=1<<n; for (reg i=0; i<n; ++i) for (reg j=0; j<n; ++j) if (mp[i][j]) to[1<<i]|=1<<j; for (reg s=1; s<lim; ++s) { if (s!=(s&-s)) to[s]=to[s^(s&-s)]&to[s&-s]; if (vis[s]) {--ans; continue;} for (reg i=to[s]; i; i=(i-1)&to[s]) vis[s|i]=1; } printf("%d\n", ans); } } signed main() { int T; T=read(); while (T--) { //memset(mp, 0, sizeof(mp)); memset(head, -1, sizeof(head)); n=read(); for (reg i=0; i<n; ++i) for (reg j=0; j<n; ++j) { mp[i][j]=read(); //if (read()) add(i, j); } //force::solve(); //task1::solve(); task::solve(); } return 0; }
这篇关于题解 竞赛图的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)