1093: [ZJOI2007]最大半连通子图
Time Limit: 30 Sec Memory Limit: 162 MB
Submit: 1962 Solved: 787
[Submit][Status][Discuss]
Description
Input
第一行包含两个整数N，M，X。N，M分别表示图G的点数与边数，X的意义如上文所述。接下来M行，每行两个正整数a, b，表示一条有向边(a, b)。图中的每个点将编号为1,2,3…N，保证输入中同一个(a,b)不会出现两次。
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
HINT
对于100%的数据， N ≤100000, M ≤1000000；对于100%的数据， X ≤10^8。
Source
这题我几月前刚学Tarjan时就想做了，但是看到是ZJOI的题就放弃了。。（果真生在浙江就是悲催）
这题当年应该是二试的第一题难度还好，当然对于神犇来说应该就是水题了。。
题意为求最大半联通子图，就是求图上最长链，知道这点就好做了
先对原图强连通缩点（傻逼的我竟然连Tarjan都写错了WA了一发
），然后在新图上拓扑排序，记录一下每一个点的信息进行转移
细节：注意新图上可能有重边。
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 100010
#define M 1000010
using namespace std;
int head[N],Head[N],dfn[N],low[N],stack[N],belong[N],vis[N],f[N],g[N],num[N],In[N],q[M];
int n,m,X,u,v,ans,mx,cnt,tot,top,sum;
struct data{int u,v,next;} e[M],w[M];
int read(){
int x = 0,f = 1,c = getchar();
while (c<'0' || c>'9'){if (c=='-') f = -1;c = getchar();}
while (c>='0' && c<='9') x = x*10+c-'0',c = getchar();
return x*f;
}
void Insert(int u,int v){
e[++cnt].u = u;e[cnt].v = v;
e[cnt].next = head[u];head[u] = cnt;
}
void Ins(int u,int v){
w[++cnt].u = u;w[cnt].v = v;
w[cnt].next = Head[u];Head[u] = cnt;
In[v]++;
}
void Tarjan(int u){
dfn[u] = low[u] = ++tot;
stack[++top] = u;
vis[u] = 1;
for (int i=head[u];i;i=e[i].next){
int v = e[i].v;
if (!dfn[v]){
Tarjan(v);
low[u] = min(low[u],low[v]);
}
else if (vis[v]) low[u] = min(low[u],dfn[v]);
}
if (dfn[u]==low[u]){
sum++;
int v = -1;
while (u!=v){
v = stack[top--];
belong[v] = sum;
num[sum]++;
vis[v] = 0;
}
}
}
void Rebuild(){
cnt = 0;
for (int x=1;x<=n;x++)
for (int i=head[x];i;i=e[i].next)
if (belong[x]!=belong[e[i].v])
Ins(belong[x],belong[e[i].v]);
}
void DP(){
memset(vis,0,sizeof(vis));
int h = 0,t = 0;
for (int i=1;i<=sum;i++){
if (!In[i]) q[++t] = i;
f[i] = num[i];g[i] = 1;
}
while (h<t){
int now = q[++h];
for (int i=Head[now];i;i=w[i].next){
In[w[i].v]--;
if (!In[w[i].v]) q[++t] = w[i].v;
if (vis[w[i].v]==now) continue;
if (f[now]+num[w[i].v]>f[w[i].v]){
f[w[i].v] = f[now]+num[w[i].v];
g[w[i].v] = g[now];
}
else if (f[now]+num[w[i].v]==f[w[i].v]) (g[w[i].v]+=g[now])%=X;
vis[w[i].v] = now;
}
}
}
int main(){
n = read();m = read();X = read();
for (int i=1;i<=m;i++){
int u = read(),v = read();
Insert(u,v);
}
for (int i=1;i<=n;i++)
if (!dfn[i]) Tarjan(i);
Rebuild();
DP();
for (int i=1;i<=sum;i++){
if (f[i]>mx) mx = f[i],ans = g[i];
else if (f[i]==mx) (ans+=g[i])%=X;
}
printf("%d\n%d",mx,ans);
}
评论 (0)
