Tarjan水题系列(5):最大半连通子图 [ZJOI2007 luogu P2272]
2024-09-03 00:07:22
大意:
缩点后转为求最长链的长度和最长链的个数
思路:
看懂题就会做系列 长度和个数都可以拓扑排序后DP求得 毕竟是2007年的题
代码:
如下
#include <cstdio>
#include <iostream>
#include <memory.h>
#define r(x) x=read()
#define MAXX 100005
#define MIN(a,b) (a<b?a:b)
#define MAX(a,b) (a>b?a:b)
#define re register
using namespace std;
typedef long long ll;
int read()
{
char ch=;int w=;
while(ch<''||ch>''){ch=getchar();}
while(ch>=''&&ch<=''){w=w*+ch-'';ch=getchar();}
return w;
}
int low[MAXX],dfn[MAXX],k,id[MAXX],num,top,sta[MAXX],du[MAXX];
int h2[MAXX],h[MAXX],u,to,cnt,book[MAXX],heap,sta2[MAXX];
int X,dp[MAXX],ans,w[MAXX],ans2[MAXX];
int n,m;
struct edge{int to,nex;}e[MAXX<<],e2[MAXX<<];
void add(int u,int to,int x)
{
cnt++;
if(x==) {e2[cnt]=(edge){to,h2[u]};h2[u]=cnt;}
if(x==) {e[cnt]=(edge){to,h[u]};h[u]=cnt;}
}
void tarjan(int now)
{
low[now]=dfn[now]=++k;
sta[++top]=now;
for(int i=h2[now];i;i=e2[i].nex)
{
if(!dfn[e2[i].to])
tarjan(e2[i].to),low[now]=MIN(low[now],low[e2[i].to]);
else
if(!id[e2[i].to])
low[now]=MIN(low[now],dfn[e2[i].to]);
}
if(dfn[now]==low[now])
{
id[now]=++num;
while(sta[top]!=now){id[sta[top]]=num;--top;}
top--;
}
}
int main()
{
r(n),r(m),r(X);
for(re int i=;i<=m;++i)
r(u),r(to),add(u,to,);
for(re int i=;i<=n;++i)
if(!dfn[i])
tarjan(i);
for(re int i=;i<=n;++i)
w[id[i]]++;
cnt=;
for(re int i=;i<=n;++i)
for(re int j=h2[i];j;j=e2[j].nex)
{
int y=id[e2[j].to],x=id[i];
if(x!=y) add(x,y,),du[y]++;
}
for(re int i=;i<=num;++i)
if(!du[i]) sta[++top]=i,dp[i]=w[i],ans2[i]=;
for(re int i=;i<=top;++i)
{
int x=sta[i];
for(re int j=h[x];j;j=e[j].nex)
{
du[e[j].to]--;
if(du[e[j].to]==) sta[++top]=e[j].to;
if(book[e[j].to]) continue;
book[e[j].to]=,sta2[++heap]=e[j].to;
if(dp[e[j].to]<dp[x]+w[e[j].to])
dp[e[j].to]=dp[x]+w[e[j].to],ans2[e[j].to]=;
if(dp[e[j].to]==dp[x]+w[e[j].to])
ans2[e[j].to]=(ans2[e[j].to]+ans2[x])%X;
}
while(heap){book[sta2[heap]]=;heap--;}
ans=MAX(ans,dp[x]);
}
ll anse=;
for(int i=;i<=num;++i)
if(dp[i]==ans) anse=(anse+ans2[i])%X;
printf("%d\n%lld",ans,anse);
return ;
}
最新文章
- C#多线程之线程同步篇1
- Jexus 支持PHP的三种方式
- 前端学习 第四弹: HTML(一)
- 团队项目——站立会议DAY9
- ApexSQL Log-SQL误操作恢复工具
- 黑马程序员——OC语言 其他语法
- Rap 安装和配置
- Could not load file or assembly &#39;MagickNet.dll&#39;
- Standalone HBase
- java 学习基础学习单词及java关键词
- PowerShell查询sql server
- 自己动手搭建Nginx+memcache+xdebug+php运行环境绿色版 For windows版
- 小记:css特殊性
- 使用Boost库中的组件进行C++内存管理
- Opencv在mac系统的安装与试用
- Java: How to resolve Access Restriction error
- 微信中音乐播放在ios不能自动播放解决
- Spring众多jar包的特点,及Spring jar包官网下载方法
- 【HDFS API编程】第一个应用程序的开发-创建文件夹
- TimeUnit类中的sleep() 和Thread.sleep()