【题解】【BZOJ】AGC008F Blackout
2021/9/1 23:10:54
本文主要是介绍【题解】【BZOJ】AGC008F Blackout,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
AGC006F Blackout
AGC006F Blackout
1 题外话
什么神仙题目
2 sol
对黑格子\((x,y)\) ,连一条\(x->y\) 的边
此时问题变为如果存在\(x->y,y->z\) 的边,那么添加一条\(z->x\) 的边,最后统计总共有多少条边
现在我们只考虑每个弱连通块怎么统计
尝试对每一个弱连通块三色染色
2.1 无法染色
此时的图中一定有二元环/自环
经过一次操作后二元环能构造出自环,而自环能在若干次操作后将当前弱联通块变为完全图
2.2 不完全染色(用不到第二种或第三种颜色)
此时图中不会出现新边
2.3 染色成功
此时连通块的边数为\(1->2、2->3、3->1\) 的边数总和
3 code
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #define int long long using namespace std; const int N=100010; const int M=100010; inline void read(int &x) { x=0; int f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if (ch=='-') { f=-1; } ch=getchar(); } while(ch>='0'&&ch<='9') { x=x*10+ch-'0'; ch=getchar(); } x*=f; } struct note { int t; int next; int val; }; int cnt; int head[N]; note e[M<<1]; inline void add(int x,int y,int val) { e[++cnt].t=y; e[cnt].next=head[x]; e[cnt].val=val; head[x]=cnt; } int n,m; int vis[N]; int f[3],siz; int edg; bool lab; void dfs(int p,int v) { vis[p]=v; f[v]++; siz++; for(int i=head[p];i+1;i=e[i].next) { int t=e[i].t; if (e[i].val==1) { edg++; } if (vis[t]==-1) { dfs(t,(v+e[i].val)%3); } else if (vis[t]!=(vis[p]+e[i].val)%3) { lab=0; } } } int ans; signed main() { read(n),read(m); memset(head,-1,sizeof(head)); for(int i=1;i<=m;i++) { int x,y; read(x),read(y); add(x,y,1); add(y,x,2); } memset(vis,-1,sizeof(vis)); for(int i=1;i<=n;i++) { if (vis[i]==-1) { lab=1; f[0]=f[1]=f[2]=0; siz=edg=0; dfs(i,0); if (lab) { if (min(f[0],min(f[1],f[2]))==0) { ans+=edg; } else { ans+=f[0]*f[1]+f[1]*f[2]+f[2]*f[0]; } } else { ans+=siz*siz; } } } printf("%lld\n",ans); return 0; }
4 注意
打得挺长(
Created: 2021-09-01 周三 20:50
Validate
这篇关于【题解】【BZOJ】AGC008F Blackout的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升