bzoj 1039最大半联通子图缩点+dp

这题我开了三个链表

第一个是临界表

第二个是缩点后的临界表

第三个是hash表判重边

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
#define ll long long
#define maxm 1001020
#define maxn 110000
int nn,nn1,nn2,n,m,mod;
int e[maxn],ne[maxm],v[maxm];
int e1[maxn],ne1[maxm],v1[maxm];
int e2[maxm],ne2[maxm],v2[maxm],u2[maxm];
void add(int x,int y){
ne[++nn]=e[x],e[x]=nn,v[nn]=y;
}
void add1(int x,int y){
ne1[++nn1]=e1[x],e1[x]=nn1,v1[nn1]=y;
}
void add2(int x,int y,int z){
ne2[++nn2]=e2[x],e2[x]=nn2,v2[nn2]=z,u2[nn2]=y;
}
int tot,stn,st[maxn],low[maxn],dfn[maxn],in[maxn],been[maxn],siz[maxn],bign;
void tarjan(int x){
st[++stn]=x;
low[x]=dfn[x]=++tot;
been[x]=1;
for(int i=e[x];i;i=ne[i])
if(!dfn[v[i]]){
tarjan(v[i]);
low[x]=min(low[x],low[v[i]]);
}else if(been[v[i]])low[x]=min(low[x],dfn[v[i]]);
if(low[x]==dfn[x]){
++bign;
while(st[stn]!=x){
been[st[stn]]=0;
in[st[stn--]]=bign;
}
been[x]=0,in[x]=bign;
stn--;
}
}
int qu[maxn],he,bo,ru[maxn],dp[maxn];
ll w[maxn];
bool zhong(int x,int y){
int hash=(((ll)x*maxn)+(ll)y) %maxm;
for(int i=e2[hash];i;i=ne2[i])if(u2[i]==x&&v2[i]==y)return 1;
return 0;
}
void put(int x,int y){
int hash=(((ll)x*maxn)+(ll)y) %maxm;
add2(hash,x,y);
}
int maxx;
int main(){
scanf("%d%d%d",&n,&m,&mod);
for(int i=1;i<=m;i++){
int a,b;
scanf("%d%d",&a,&b);
add(a,b);
}
for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i);
for(int i=1;i<=n;i++){
siz[in[i]]++;
for(int j=e[i];j;j=ne[j]){
if(in[i]!=in[v[j]]&&!zhong(in[i],in[v[j]])){
put(in[i],in[v[j]]);
add1(in[i],in[v[j]]);
ru[in[v[j]]]++;
}
}
}
for(int i=1;i<=bign;i++)if(!ru[i])qu[++he]=i,w[i]=1,dp[i]=siz[i];
bo=1;
while(he>=bo)for(int i=e1[qu[bo++]];i;i=ne1[i]){
ru[v1[i]]--;
if(!ru[v1[i]])qu[++he]=v1[i];
}
for(int i=1;i<=he;i++){
int k=qu[i];
maxx=max(maxx,dp[k]);
for(int j=e1[k];j;j=ne1[j])dp[v1[j]]=max(dp[v1[j]],dp[k]+siz[v1[j]]);
}
for(int i=1;i<=he;i++){
int k=qu[i];
for(int j=e1[k];j;j=ne1[j])if(dp[k]+siz[v1[j]]==dp[v1[j]])w[v1[j]]+=w[k],w[v1[j]]%=mod;
}
ll ans=0;
for(int i=1;i<=bign;i++)if(dp[i]==maxx)ans+=w[i],ans%=mod;
cout<<maxx<<endl<<ans;
}

bzoj 1039最大半联通子图缩点+dp,,5-wow.com