P2272 [ZJOI2007]最大半连通子图
题目描述
一个有向图(G=(V,E))称为半连通的((Semi-Connected))，如果满足：(forall u,v in V)，满足(u o v)或(v o u)，即对于图中任意两点(u)，(v,)存在一条(u)到(v)的有向路径或者从(v)到(u)的有向路径。若(G'=(V',E'))满足(V' in V)，(E')是(E)中所有跟(V')有关的边，则称(G')是(G)的一个导出子图。若(G')是(G)的导出子图，且(G')半连通，则称(G')为(G)的半连通子图。若(G')是(G)所有半连通子图中包含节点数最多的，则称(G')是(G)的最大半连通子图。给定一个有向图(G)，请求出(G)的最大半连通子图拥有的节点数(K)，以及不同的最大半连通子图的数目(C)。由于(C)可能比较大，仅要求输出(C)对(X)的余数。
输入输出格式
输入格式：
第一行包含两个整数(N)，(M)，(X)。(N)，(M)分别表示图(G)的点数与边数，X的意义如上文所述接下来(M)行，每行两个正整数(a),(b)，表示一条有向边((a,b))。图中的每个点将编号为(1,2,3…N)，保证输入中同一个((a,b))不会出现两次。
输出格式：
应包含两行，第一行包含一个整数(K)。第二行包含整数(C) (Mod) (X).
说明
对于100%的数据， (N le 100000, M le 1000000, X le 10^8)
这种题先缩点都成套路了吧
考虑在一个有向无环图中半联通图是什么，结果是一条链，直接做DP就行了
但是！！
这个题一定要考虑重边
Code：
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define ll long long
using namespace std;
const int N=100010;
const int M=1000010;
int head0[N],Next0[M],to0[M],cnt0;
void add0(int u,int v)
{
Next0[++cnt0]=head0[u];to0[cnt0]=v;head0[u]=cnt0;
}
int head[N],Next[M],to[M],cnt;
void add(int u,int v)
{
Next[++cnt]=head[u];to[cnt]=v;head[u]=cnt;
}
int dfn[N],low[N],in[N],s[N],ha[N],siz[N],time,tot;
int n,m,n_,cntt;
ll p;
pair <int,int > e[M];
void tarjan(int now)
{
dfn[now]=low[now]=++time;
s[++tot]=now;
in[now]=1;
for(int i=head0[now];i;i=Next0[i])
{
int v=to0[i];
if(!dfn[v])
{
tarjan(v);
low[now]=min(low[now],low[v]);
}
else if(in[v])
low[now]=min(low[now],dfn[v]);
}
if(low[now]==dfn[now])
{
int k,Siz=0;
n_++;
do
{
k=s[tot--];
Siz++;
ha[k]=n_;
in[k]=0;
}while(k!=now);
siz[n_]=Siz;
}
}
void New()
{
for(int i=1;i<=n;i++)
{
for(int j=head0[i];j;j=Next0[j])
{
int v=to0[j];
if(ha[v]!=ha[i])
e[++cntt]=make_pair(ha[i],ha[v]);
}
}
sort(e+1,e+1+cntt);
cntt=unique(e+1,e+1+cntt)-(e+1);
for(int i=1;i<=cntt;i++)
{
in[e[i].second]++;
add(e[i].first,e[i].second);
}
}
void init()
{
scanf("%d%d%lld",&n,&m,&p);
int u,v;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&u,&v);
add0(u,v);
}
for(int i=1;i<=n;i++)
if(!dfn[i])
tarjan(i);
memset(in,0,sizeof(in));
New();
}
ll Cnt[N],ans;
int dp[N],mx;
queue <int > q;
void work()
{
for(int i=1;i<=n_;i++)
if(!in[i])
{
q.push(i);
dp[i]=siz[i];
mx=max(mx,dp[i]);
Cnt[i]=1;
}
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=head[u];i;i=Next[i])
{
int v=to[i];
if(dp[v]<dp[u]+siz[v])
{
dp[v]=dp[u]+siz[v];
Cnt[v]=Cnt[u];
mx=max(mx,dp[v]);
}
else if(dp[v]==dp[u]+siz[v])
(Cnt[v]+=Cnt[u])%=p;
in[v]--;
if(!in[v]) q.push(v);
}
}
for(int i=1;i<=n_;i++)
if(dp[i]==mx)
(ans+=Cnt[i])%=p;
printf("%d
%lld
",mx,ans);
}
int main()
{
init();
work();
return 0;
}
2018.7.26