bzoj1093 [ZJOI2007]最大半联通子图 缩点 + 拓扑序
2024-10-21 02:45:56
最大半联通子图对应缩点后的$DAG$上的最长链
复杂度$O(n + m)$
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std; extern inline char gc() {
static char RR[], *S = RR + , *T = RR + ;
if(S == T) fread(RR, , , stdin), S = RR;
return *S ++;
}
inline int read() {
int p = , w = ; char c = gc();
while(c > '' || c < '') { if(c == '-') w = -; c = gc(); }
while(c >= '' && c <= '') p = p * + c - '', c = gc();
return p * w;
} #define ri register int
#define sid 1005000 int n, m, id, nid, cnp, mod, top;
int pre[sid], nxt[sid], node[sid], cap[sid], vis[sid];
int low[sid], dfn[sid], st[sid], ins[sid], cnt[sid], b[sid], deg[sid], q[sid]; inline void addedge(int u, int v) {
nxt[++ cnp] = cap[u]; cap[u] = cnp;
pre[cnp] = u; node[cnp] = v; deg[v] ++;
} void tarjan(int o, int fa) {
low[o] = dfn[o] = ++ id; st[++ top] = o; ins[o] = ;
#define cur node[i]
for(int i = cap[o]; i; i = nxt[i]) {
if(!dfn[cur]) tarjan(cur, o), low[o] = min(low[o], low[cur]);
else if(ins[cur]) low[o] = min(low[o], dfn[cur]);
}
if(dfn[o] == low[o]) {
int p; ++ nid;
do{ p = st[top --]; b[p] = nid;
ins[p] = ; cnt[nid] ++;
} while(p != o);
}
} inline void inc(int &a, int b)
{ a += b; if(a >= mod) a -= mod; } struct dp {
int sz, num;
friend void cmax(dp &a, dp b) {
if(b.sz > a.sz) a = b;
else if(b.sz == a.sz) inc(a.num, b.num);
}
} f[sid]; void top_dp() {
int fr = , to = ;
for(ri i = ; i <= nid; i ++) {
if(!deg[i]) q[++ to] = i;
f[i] = { cnt[i], };
}
#define cur node[i]
while(fr <= to) {
int o = q[fr ++];
for(ri i = cap[o]; i; i = nxt[i]) {
deg[cur] --; if(!deg[cur]) q[++ to] = cur;
if(vis[cur] == o) continue;
cmax(f[cur], (dp){ f[o].sz + cnt[cur], f[o].num } );
vis[cur] = o;
}
}
dp ans = { , };
for(ri i = ; i <= nid; i ++) cmax(ans, f[i]);
printf("%d\n%d\n", ans.sz, ans.num);
} int main() {
n = read(); m = read(); mod = read();
for(ri i = ; i <= m; i ++) {
int u = read(), v = read();
addedge(u, v);
}
for(ri i = ; i <= n; i ++)
if(!dfn[i]) tarjan(i, );
memset(cap, , (n + ) << );
memset(deg, , (n + ) << );
int cno = cnp; cnp = ;
for(ri i = ; i <= cno; i ++)
if(b[pre[i]] != b[node[i]]) addedge(b[pre[i]], b[node[i]]);
top_dp();
return ;
}
最新文章
- Spring的事务管理
- python---set集合
- 在MAVEN仓库中添加ORACLE JDBC驱动
- HDU 1284 思维上的水题
- Spout数据源
- C# 轮循回调
- HDU1172(枚举)
- 看Instgram课程分享笔记
- [Swift]LeetCode447. 回旋镖的数量 | Number of Boomerangs
- Linux_Ubuntu_C++编程_如何完成一个C++编写,调试,运行。
- 深入理解 ES6中的 Reflect
- 【blog】SpringMVC返回RSS格式的XML数据
- PostgreSQL在Update时使用Substring函数截取字符串并且加上CASE WHEN THEN条件判断
- IDLE的GUI交互模式下完美清屏
- C++ 操作符、局部 全局变量及自动转换原则
- Ulua_toLua_基本案例(二)_ScriptsFromFile
- Hololens 开发环境配置(转)
- PHPhotos
- 【错误记录】python logging日志打印俩次的原因
- c#递归生成XML
热门文章
- 2016-2017-2 20155117实验二《Java面向对象程序设计》实验报告
- c++ virtual总结
- TinyOS在ubuntu 14.04下安装教程
- docker ubuntu容器更换阿里源(转)
- app 测试基础
- 【Python学习】csv库
- queue_delayed_work和queue_work区别 (转http://blog.csdn.net/dosculler/article/details/7968101)
- iscsi服务器的搭建
- SilverLight高亮显示文本
- TCP三次链接和四次断开