题解 P2272 【[ZJOI2007]最大半连通子图】
就要氮氧碘磷8102了有点慌
最近在用某本蓝色的一本通练习tarjan时,看到了这道题,于是现在loj上打开了这道题,题目上给了半连通的定义,和强联通的定义好像啊,然后看这又是tarjan的练习,于是冷静分析,一个强连通分量肯定是一个半连通子图呀.
于是想先缩点再说
void tarjan(int t)
{
//个人喜好用order数组,一般是dfn
order[t]=low[t]=++timetag;
zh[++top]=t;b[t]=1;
int temp;
for(register int i=headf[t];i;i=edgef[i].next)
{
if(!order[edgef[i].to])
{
tarjan(edgef[i].to);
low[t]=min(low[edgef[i].to],low[t]);
}
else if(b[edgef[i].to])
low[t]=min(low[t],order[edgef[i].to]);
}
if(low[t]==order[t])
{
while((temp=zh[top--]))
{
b[temp]=0;
root[temp]=t;
++size[t];//统计这个强联通分量(半连通子图)内的点数
if(t==temp)
break;
}
}
}以上是tarjan常规操作,不懂的没关系先去缩点
好,缩完点了.但并不是仅仅只有强联通子图是半连通子图
那我们考虑在DAG(有向无环图)已经是了上,怎么求半连通图呢?
由半连通图的定义稍稍想一想可知,只要两个点有边相连,那他们就可以放到一个半连通子图里,所以我们只要在缩完点的新图上一直进行这种操作就可以了.
因为新图已经是一个DAG了,那么一直进行这种操作是不会形成环的.那么求最大半连通子图不就是求最长链吗美滋滋然后题目又要求最大半连通子图的方案数,我们很容易由做缩点这道题的经验想到拓扑排序.
void topsort()
{
//r是用来统计入度,c是用来统计出度的
//喜欢用首写字母,大佬勿喷
queue<int> q;
cnt=0;
for(register int i=1;i<=n;i++)
if(root[i]==i&&!r[i])//是强连通分量的根
q.push(i),dis[i]=size[i],ans[i]=1;
while(q.size())
{
int t=q.front();
q.pop();
for(register int i=heads[t];i;i=edges[i].next)
{
if(dis[edges[i].to]<dis[t]+size[edges[i].to])
//更长的链,长度和方案数都直接更新
dis[edges[i].to]=dis[t]+size[edges[i].to],ans[edges[i].to]=ans[t];
else if(dis[edges[i].to]==dis[t]+size[edges[i].to])
ans[edges[i].to]=(ans[edges[i].to]%mo+ans[t]%mo)%mo;
//相同的长度,直接方案数累加
--r[edges[i].to];
if(!r[edges[i].to])//入度为0了就入队
q.push(edges[i].to);
}
}
for(register int i=1;i<=n;i++)
if(root[i]==i&&!c[i])
{
if(dis[i]==ans1)
ans2=(ans2%mo+ans[i]%mo)%mo;
if(dis[i]>ans1)
ans1=dis[i],ans2=ans[i];
}
}拓扑排序上稍加变动,和缩点模板题的拓扑排序差不多吧(除了统计方案数)
但是这道题就这样结束了吗?不存在的
如果这个缩完点之后的图中出现了重边怎么办,那就会使方案数莫名增多.所以对于缩完点后的图还要判重边
inline bool cmp(zhzs x,zhzs y)
{return x.x==y.x?(x.y<y.y):(x.x<y.x);}for(register int i=1;i<=m;i++)
{
int x1=root[edgef[i].from];
int y1=root[edgef[i].to];
if(x1!=y1)
{
e[++num].x=x1;
e[num].y=y1;
}
}
sort(e+1,e+num+1,cmp);for(register int i=1;i<=num;i++)
if(e[i].x!=e[i-1].x||e[i].y!=e[i-1].y)
{
adds(e[i].x,e[i].y);
}直接让起点相同的边以终点大小顺序排序,然后只要这条边的起点或者终点与上一条不同就不是重边
所以这道题就弄完了
附上我丑陋的代码:
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
struct ppp
{int x,y;}e[2000301];
struct node
{int to,from,next;}edgef[2000301],edges[2000301];
int n,m,x,y,top,cnt,num,timetag,mo,ans1,ans2;
int dis[1000001],ans[1000001],headf[1000001],heads[1000001];
int zh[1000001],size[1000001],b[1000001];
int order[1000001],low[1000001],root[1000001],r[1000001],c[1000001];
//别慌,没有炸空间
inline bool cmp(zhzs x,zhzs y)
{return x.x==y.x?(x.y<y.y):(x.x<y.x);}//去重边,排序
inline void addf(int u,int v)//原图加边
{edgef[++cnt].to=v;edgef[cnt].from=u;edgef[cnt].next=headf[u];headf[u]=cnt;}
inline void adds(int u,int v)//新图加边
{edges[++cnt].to=v;edges[cnt].next=heads[u];heads[u]=cnt;}
inline int min(int x,int y)
{return x<y?x:y;}
//没什么用的重载
void tarjan(int t)
{
order[t]=low[t]=++timetag;//时间戳
zh[++top]=t;b[t]=1;
int temp;
for(register int i=headf[t];i;i=edgef[i].next)
{
if(!order[edgef[i].to])
{
tarjan(edgef[i].to);
low[t]=min(low[edgef[i].to],low[t]);
}
else if(b[edgef[i].to])
low[t]=min(low[t],order[edgef[i].to]);
}
if(low[t]==order[t])
{
while((temp=zh[top--]))//弹栈
{
b[temp]=0;
root[temp]=t;
++size[t];//统计这个强联通分量(半连通子图)内的点数
if(t==temp)
break;
}
}
}
void topsort()
{
queue<int> q;
cnt=0;
for(register int i=1;i<=num;i++)
if(e[i].x!=e[i-1].x||e[i].y!=e[i-1].y)
{
adds(e[i].x,e[i].y);
++r[e[i].y];++c[e[i].x];//统计入度,出度
}
for(register int i=1;i<=n;i++)
if(root[i]==i&&!r[i])
q.push(i),dis[i]=size[i],ans[i]=1;
while(q.size())
{
int t=q.front();
q.pop();
for(register int i=heads[t];i;i=edges[i].next)
{
if(dis[edges[i].to]<dis[t]+size[edges[i].to])
dis[edges[i].to]=dis[t]+size[edges[i].to],ans[edges[i].to]=ans[t];
else if(dis[edges[i].to]==dis[t]+size[edges[i].to])
ans[edges[i].to]=(ans[edges[i].to]%mo+ans[t]%mo)%mo;
--r[edges[i].to];
if(!r[edges[i].to])
q.push(edges[i].to);
}
}
for(register int i=1;i<=n;i++)
if(root[i]==i&&!c[i])
{
if(dis[i]==ans1)
ans2=(ans2%mo+ans[i]%mo)%mo;
if(dis[i]>ans1)
ans1=dis[i],ans2=ans[i];
}
}
int main()
{
scanf("%d%d%d",&n,&m,&mo);
for(register int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
addf(x,y);
}
for(register int i=1;i<=n;i++)
if(!order[i])//还没有被访问过
tarjan(i);
for(register int i=1;i<=m;i++)
{
int x1=root[edgef[i].from];
int y1=root[edgef[i].to];
if(x1!=y1)//判断是否在同一个强连通分量内
{
e[++num].x=x1;
e[num].y=y1;
}
}
sort(e+1,e+num+1,cmp);
topsort();
printf("%d\n%d",ans1,ans2);
return 0;
}一开始先在loj上A了,就想洛谷上应该有名字这么高级的题吧,于是到洛谷上一找.
我的天! ZJOI 我的天! 紫题,我又要A紫题了.
结果一交上去RE,有点难受,然后看了一下数组没毛病啊,就一直瞎jb乱调,然并卵啊,最后还是想把数组开大十倍,碰个运气吧,结果A了,有点舒服
第一篇紫题题解,大佬勿喷,关爱蒟蒻