【POI 每日题解 #4】 [POI2008]MAF-Mafia
2024-10-16 13:22:46
很容易看出是拓扑 但不容易想出来怎么做【可能是我太菜
首先 入度为零的人是肯定死不了的
接着 我们分成环和链分析
对于一个链
最多的情况就是顺着一个个开枪 最后剩一个( (n - 1) -> (n), (n - 2) ->(n - 1) …… )
最少的情况就是死一半(1->2, 3->4……)
对于一个环
它和链基本上一样
区别在于从任何一个人开始都不会影响结果
这个性质很有用
因为当有环接在链上时
最多的情况下环上的点会全部挂掉
void bfs(){
for(int i = ; i <= n; i++)
if(!ind[i]){
q[++ans1] = i;
ans2++;
}
for(int i = ; i <= ans1; i++){
int fro = aim[q[i]];
if(vis[fro]) continue;
ind[aim[fro]]--;
vis[fro] = ;
otd[aim[fro]] = ;
if(!ind[aim[fro]]) q[++ans1] = aim[fro];
}//删链过程 非常重要!
for(int i = ; i <= n; i++)
if(!vis[i] && ind[i]){
int len = , flag = ;
for(int j = i; !vis[j]; j = aim[j]){
vis[j] = ;
len++;
flag |= otd[j];
}
//printf("%d %d\n", flag, len);
ans1 += (len >> );
if(len > && !flag) ans2++;
}
}
关键部分
最新文章
- 匹夫细说C#:不是“栈类型”的值类型,从生命周期聊存储位置
- ACM好书推荐
- SQL Server中的事务日志管理(3/9):事务日志,备份与恢复
- php Composer 报ssl证书错误
- Windows不能在本地计算机启动OracleDBConsoleorcl .错误代码2
- cordova-plugin-app-version插件使用
- <;context:component-scan>;
- Python的.py文件打包成exe可执行文件
- 用IO创建并格式化分区
- python抓取电影<;海王>;影评词云生成
- luogu2643 聪聪可可
- LINQ Group By操作(转载)
- Django----From组件
- WordPress基础:常用分类列表wp_list_categories
- react中的hoc和修饰器@connect结合使用
- HTML 求阶乘之和
- sql子查询在insert、update、delete中的应用
- 几种Python执行时间的计算方法
- SparkSQL大数据实战:揭开Join的神秘面纱
- 2018百度之星开发者大赛-paddlepaddle学习
热门文章
- 来不及说什么了,Python 运维开发剁手价仅剩最后 2 天
- 给echarts加个“全屏展示”
- 【亲测有效】运行docker ps 出现Got permission denied问题的解决方案
- Docker容器学习梳理 - 私有仓库Registry使用
- 个人博客作业_week3
- 毕业设计 之 三 mooodle及bigbluebutton使用笔记(未完成)
- Linux内核设计第十七章笔记
- SuperMaze(Hello World 团队)Alpha版使用说明
- [福大软工] Z班 评测作业对应表
- chrome启用flash不询问