Bzoj1093 [zjoi2007]最大半连通子图

Posted by yjjr's blog on February 6, 2018

标签:tarjan缩点,DP,拓扑排序

Description

  一个有向图G=(V,E)称为半连通的(Semi-Connected),如果满足:?u,v∈V,满足u→vv→u,即对于图中任意
两点uv,存在一条uv的有向路径或者从vu的有向路径。若G'=(V',E')满足V'?VE'E中所有跟V'有关的边,
则称G'G的一个导出子图。若G'G的导出子图,且G'半连通,则称G'G的半连通子图。若G'G所有半连通子图
中包含节点数最多的,则称G'G的最大半连通子图。给定一个有向图G,请求出G的最大半连通子图拥有的节点数K
,以及不同的最大半连通子图的数目C。由于C可能比较大,仅要求输出CX的余数。

Input

  第一行包含两个整数NMXNM分别表示图G的点数与边数,X的意义如上文所述接下来M行,每行两个正整
a, b,表示一条有向边(a, b)。图中的每个点将编号为1,2,3…N,保证输入中同一个(a,b)不会出现两次。N ≤1
00000, M ≤1000000
;对于100%的数据, X≤10^8

Output

  应包含两行,第一行包含一个整数K。第二行包含整数C Mod X.

Sample Input

6 6 20070603

1 2

2 1

1 3

2 4

5 6

6 4

Sample Output

3

3

 

分析:先tarjan缩点,之后重建一个图,然后DP和拓扑排序跑最长链

Code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define LL long long
#define mem(x,num) memset(x,num,sizeof x)
using namespace std;
inline LL read()
{
	LL f=1,x=0;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();}
	return x*f;
}
const int maxn=1e5+6,maxm=2e6+6;
int mx,ans,ind,cnt,scc,top,m,n,mod;
int head[maxn],head2[maxn],dfn[maxn],low[maxn],hav[maxn],belong[maxn];
int r[maxn],f[maxn],g[maxn],vis[maxn],q[maxn];
bool inq[maxn];
struct edge{int to,next;}e[maxm],ed[maxm];
void tarjan(int x)
{
	dfn[x]=low[x]=++ind;
	q[++top]=x;inq[x]=1;
#define reg(x) for(int i=head[x];i;i=e[i].next)
#define v e[i].to
	reg(x)
	    if(!dfn[v])tarjan(v),low[x]=min(low[x],low[v]);
		else if(inq[v])low[x]=min(low[x],dfn[v]);
	int now=0;
	if(low[x]==dfn[x]){
		scc++;
		while(now!=x){
			now=q[top];top--;
			inq[now]=0;
			hav[scc]++;
			belong[now]=scc;
		}
	}
}
void rebuild()
{
	cnt=0;
	rep(x,1,n)
	    reg(x)
			if(belong[x]!=belong[v])ed[++cnt]=(edge){belong[v],head2[belong[x]]},head2[belong[x]]=cnt,r[belong[v]]++;
}
void dp()
{
	int head=0,tail=0;
	rep(i,1,scc){
		if(!r[i])q[tail++]=i;
		f[i]=hav[i];g[i]=1;
	}
	while(head<tail){
		int now=q[head++];
#define reg2(x) for(int i=head2[x];i;i=ed[i].next)
#define v2 ed[i].to
		reg2(now){
			r[v2]--;
			if(!r[v2])q[tail++]=v2;
			if(vis[v2]==now)continue;
			if(f[now]+hav[v2]>f[v2]){
				f[v2]=f[now]+hav[v2];
				g[v2]=g[now];
			}
			else if(f[now]+hav[v2]==f[v2])g[v2]=(g[v2]+g[now])%mod;
			vis[v2]=now;
		}
	}
}
int main()
{
	n=read(),m=read(),mod=read();
	rep(i,1,m){
		int u=read(),V=read();
		e[++cnt]=(edge){V,head[u]};head[u]=cnt;
	}
	rep(i,1,n)
	    if(!dfn[i])tarjan(i);
	rebuild();
	dp();
	rep(i,1,scc){
		if(f[i]>mx)mx=f[i],ans=g[i];
		else if(f[i]==mx)ans=(ans+g[i])%mod;
	}
	cout<<mx<<endl<<ans<<endl;
	return 0;
}


本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr