Description
一个有向图G=(V,E)称为半连通的(Semi-Connected),如果满足:?u,v∈V,满足u→v或v→u,即对于图中任意
两点u,v,存在一条u到v的有向路径或者从v到u的有向路径。若G'=(V',E')满足V'?V,E'是E中所有跟V'有关的边,
则称G'是G的一个导出子图。若G'是G的导出子图,且G'半连通,则称G'为G的半连通子图。若G'是G所有半连通子图
中包含节点数最多的,则称G'是G的最大半连通子图。给定一个有向图G,请求出G的最大半连通子图拥有的节点数K
,以及不同的最大半连通子图的数目C。由于C可能比较大,仅要求输出C对X的余数。
Input
第一行包含两个整数N,M,X。N,M分别表示图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
1 2
2 1
1 3
2 4
5 6
6 4
Sample Output
3
3
3
正解:tarjan+DP
解题报告:
遥遥今天讲课讲了这道题,然后感觉这是最水的,就高兴地开了坑,调了半个晚上都没有发现为什么wa了。
最后发现居然是有重边!!!!!!然后方案重复计算了,但我当时没有马上想出怎么判重,于是看了网上的题解发现可以用set,我真傻真的。
做法其实挺简单,首先tarjan缩环,然后重构图,可以想到我们一定是在重构的图上选取一条链,使得链的点权和最大。DP可做。
//It is made by jump~
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <ctime>
#include <vector>
#include <queue>
#include <map>
#include <set>
#ifdef WIN32
#define OT "%I64d"
#else
#define OT "%lld"
#endif
using namespace std;
typedef long long LL;
const int MAXN = ;
const int MAXM = ;
int MOD;
int n,m,ecnt,ans,num;
int first[MAXN],to[MAXM],next[MAXM];
bool pd[MAXN];
int dfn[MAXN],low[MAXN];
int Stack[MAXN*],top,belong[MAXN];
int size[MAXN],cnt;
int head[MAXN],ru[MAXN],f[MAXN];
bool vis[MAXN]; set<pair<int,int> >bst;//要有一个空格 struct edge{
int v,next;
}e[MAXM]; inline int getint()
{
int w=,q=;
char c=getchar();
while((c<'' || c>'') && c!='-') c=getchar();
if (c=='-') q=, c=getchar();
while (c>='' && c<='') w=w*+c-'', c=getchar();
return q ? -w : w;
} inline void dfs(int x){
dfn[x]=++ecnt; low[x]=dfn[x];
pd[x]=; Stack[++top]=x;
for(int i=first[x];i;i=next[i]) {
int v=to[i];
if(!dfn[v]) { dfs(v); if(low[v]<low[x]) low[x]=low[v]; }
else if(pd[v]) low[x]=min(low[v],low[x]);
}
if(dfn[x]==low[x]){
cnt++; size[cnt]++; belong[x]=cnt; pd[x]=;
while(Stack[top]!=x&&top) belong[Stack[top]]=cnt,pd[Stack[top]]=,top--,size[cnt]++;
top--;
}
} inline void tarjan(){
ecnt=;
for(int i=;i<=n;i++) if(!dfn[i]) dfs(i);
ecnt=;
for(int i=;i<=n;i++) {
for(int j=first[i];j;j=next[j]) {
int v=to[j];
if(belong[i]!=belong[v]) {
if(bst.find(make_pair(belong[i],belong[v]))!=bst.end()) continue;
e[++ecnt].next=head[belong[i]]; head[belong[i]]=ecnt; e[ecnt].v=belong[v];
ru[belong[v]]++;
bst.insert(make_pair(belong[i],belong[v]));
}
}
}
} inline void DFS(int x){
vis[x]=;
for(int i=head[x];i;i=e[i].next) {
int v=e[i].v;
if(!vis[v]) DFS(v);
if(f[v]>f[x]) f[x]=f[v];
}
f[x]+=size[x];
} inline void DFS2(int x){
vis[x]=;
for(int i=head[x];i;i=e[i].next) {
int v=e[i].v;
if(!vis[v]) DFS2(v);
//不能有重边!!!!!!
if(f[x]==f[v]+size[x]) { dfn[x]+=dfn[v]; if(dfn[x]>=MOD) dfn[x]%=MOD; }
}
if(!head[x]) dfn[x]=;
if(f[x]==ans) { num+=dfn[x]; if(num>=MOD) num%=MOD; }
} inline void DP(){
memset(vis,,sizeof(vis));
for(int i=;i<=cnt;i++) if(!ru[i]) DFS(i),ans=max(ans,f[i]);
memset(vis,,sizeof(vis)); memset(dfn,,sizeof(dfn));
for(int i=;i<=cnt;i++)
if(!ru[i]) {
DFS2(i);
}
printf("%d\n%d",ans,num);
} inline void work(){
n=getint(); m=getint(); MOD=getint();
int x,y;
for(int i=;i<=m;i++) {
x=getint(); y=getint();
next[++ecnt]=first[x]; first[x]=ecnt; to[ecnt]=y;
}
tarjan();
DP();
} int main()
{
work();
return ;
}