首页 > 代码库 > 【BZOJ1093】【ZJOI2007】最大半连通子图 强连通分量缩点+sort去重边+拓扑排序
【BZOJ1093】【ZJOI2007】最大半连通子图 强连通分量缩点+sort去重边+拓扑排序
转载请注明出处:http://blog.csdn.net/vmurder/article/details/42610705
其实我就是觉得原创的访问量比未授权盗版多有点不爽233。。。
题解:
首先缩个点是必然,然后随便想想就知道缩点后需要最后是一条链,
也就是——
缩点后求拓扑图最长路以及方案数。
呃,去重的部分我重标号排了个序水过。
代码:
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define N 101000 #define M 1001000 #define inf 0x3f3f3f3f using namespace std; struct KSD { int v,len,next; }e[M]; int head[N],cnt; int n,m,mod; struct Road { int u,v; }road[M]; inline void add(int u,int v,int len=0) { e[++cnt].v=v; e[cnt].len=len; e[cnt].next=head[u]; head[u]=cnt; } int dfn[N],low[N]; int id[N],num[N],group; int stk[N],top; bool in[N]; void tarjan(int x) { dfn[x]=low[x]=++cnt; stk[++top]=x,in[x]=1; int i,v; for(i=head[x];i;i=e[i].next) { v=e[i].v; if(!dfn[v]) { tarjan(v); low[x]=min(low[x],low[v]); } else if(in[v])low[x]=min(low[x],dfn[v]); } if(low[x]==dfn[x]) { group++; do{ v=stk[top--]; in[v]=0; id[v]=group; num[group]++; }while(v!=x); } } int f[N],d[N]; long long cot[N]; int s,t; bool cmp(const Road &a,const Road &b){return id[a.u]==id[b.u]?id[a.v]<id[b.v]:id[a.u]<id[b.u];} void build() { int i,a,b; scanf("%d%d%d",&n,&m,&mod); for(i=1;i<=m;i++) { scanf("%d%d",&road[i].u,&road[i].v); add(road[i].u,road[i].v); } cnt=0; for(i=1;i<=n;i++)if(!dfn[i])tarjan(i); cnt=0,memset(head,0,sizeof(head)); s=0,t=group+1; for(d[t]=group,i=1;i<=group;i++)d[i]=1; for(i=1;i<=group;i++)add(s,i,num[i]),add(i,t,0); sort(road+1,road+m+1,cmp); for(i=1;i<=m;i++) { a=id[road[i].u],b=id[road[i].v]; if(a==id[road[i-1].u]&&b==id[road[i-1].v])continue; if(a==b)continue; add(a,b,num[b]); d[b]++; } } void topo_dp() { int i,u,v; stk[top=1]=s; cot[s]=1%mod; while(top) { u=stk[top--]; for(i=head[u];i;i=e[i].next) { v=e[i].v; if(f[v]<f[u]+e[i].len) { f[v]=f[u]+e[i].len; cot[v]=cot[u]; } else if(f[v]==f[u]+e[i].len) cot[v]+=cot[u],cot[v]%=mod; d[v]--; if(!d[v])stk[++top]=v; } } printf("%d\n%lld\n",f[t],cot[t]); } int main() { // freopen("test.in","r",stdin); build(); topo_dp(); return 0; }
【BZOJ1093】【ZJOI2007】最大半连通子图 强连通分量缩点+sort去重边+拓扑排序
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。