BZOJ 4562: [Haoi2016]食物链 拓扑排序
2024-09-05 07:50:52
建反图,跑一个拓扑排序dp即可.
Code:
#include <bits/stdc++.h>
#define ll long long
#define N 100005
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
ll f[N];
queue<int>q;
int edges,n,m;
int in[N],out[N],hd[N],to[N<<1],nex[N<<1],mk[N];
void add(int u,int v)
{
nex[++edges]=hd[u],hd[u]=edges,to[edges]=v;
}
int main()
{
int i,j;
// setIO("input");
scanf("%d%d",&n,&m);
for(i=1;i<=m;++i)
{
int a,b;
scanf("%d%d",&a,&b),add(b,a),++in[a],++out[b];
}
for(i=1;i<=n;++i)
{
if(in[i]==0 && out[i]!=0)
{
q.push(i),f[i]=1,mk[i]=1;
}
}
for(;!q.empty();)
{
int u=q.front();q.pop();
for(int i=hd[u];i;i=nex[i])
{
int v=to[i];
f[v]+=f[u];
--in[v];
if(in[v]==0) q.push(v);
}
}
ll ans=0;
for(i=1;i<=n;++i)
{
if(out[i]==0 && !mk[i])
{
ans+=f[i];
}
}
printf("%lld\n",ans);
return 0;
}
最新文章
- html5 Worker学习
- 职责链模式(chain of responsibility Pattern)
- Zabbix3.0 自动邮件报障
- jquery mobile 请求数据方法执行时显示加载中提示框
- SVN中的常见错误(长期更新)
- PHP中$_REQUEST中包含的数据,数据被覆盖问题
- printf, fprintf, sprintf, snprintf, vprintf, vfprintf, vsprintf, vsnprintf - 输出格式转换函数
- ios 获取字符串所需要占用的label的高度
- BJUI 转
- contextmenu
- MVC 4 插件化架构简单实现
- linux 进程命令
- centos docker 安装
- JS模块化:CommonJS和AMD(Require.js)
- 案例:通过shell脚本实现mysql数据备份与清理
- dll多个版本问题
- codevs 1004 四子连棋 BFS、hash判重
- LNMP redis 安装、PHPredis扩展配置、服务器自启动、redis认证密码
- plsql的快速生成sql语句设置
- http协议与https协议的区别
热门文章
- Go-函数高级使用-条件分支-包管理-for循环-switch语句-数组及切片-与或非逻辑符
- QAbstractItemModel使用样例与解析(Model::index使用了createIndex,它会被销毁吗?被销毁了,因为栈对象出了括号就会被销毁)
- 牛客 201 J Princess Principal (括号, 栈模拟)
- 01 Java 内存分配全面浅析
- Hash一致性算法底层原理
- JavaScript 的编译原理
- 不显示Zetero导出的文献库中的部分内容
- C# Winfrom 自定义控件添加图标
- Centos7 docker、harbor 安装配置
- delphi Tidhttp 发送json格式报文