题目 https://www.luogu.org/problemnew/show/P2272
大意:
缩点后转为求最长链的长度和最长链的个数
思路:
看懂题就会做系列 长度和个数都可以拓扑排序后 DP 求得 毕竟是 2007 年的题
代码:
如下
- #include <cstdio>
- #include <iostream>
- #include <memory.h>
- #define r(x) x=read()
- #define MAXX 100005
- #define MIN(a,b) (a<b?a:b)
- #define MAX(a,b) (a>b?a:b)
- #define re register
- using namespace std;
- typedef long long ll;
- int read()
- {
- char ch=0;int w=0;
- while(ch<'0'||ch>'9'){ch=getchar();}
- while(ch>='0'&&ch<='9'){w=w*10+ch-'0';ch=getchar();}
- return w;
- }
- int low[MAXX],dfn[MAXX],k,id[MAXX],num,top,sta[MAXX],du[MAXX];
- int h2[MAXX],h[MAXX],u,to,cnt,book[MAXX],heap,sta2[MAXX];
- int X,dp[MAXX],ans,w[MAXX],ans2[MAXX];
- int n,m;
- struct edge{int to,nex;}e[MAXX<<4],e2[MAXX<<4];
- void add(int u,int to,int x)
- {
- cnt++;
- if(x==1) {e2[cnt]=(edge){to,h2[u]};h2[u]=cnt;}
- if(x==2) {e[cnt]=(edge){to,h[u]};h[u]=cnt;}
- }
- void tarjan(int now)
- {
- low[now]=dfn[now]=++k;
- sta[++top]=now;
- for(int i=h2[now];i;i=e2[i].nex)
- {
- if(!dfn[e2[i].to])
- tarjan(e2[i].to),low[now]=MIN(low[now],low[e2[i].to]);
- else
- if(!id[e2[i].to])
- low[now]=MIN(low[now],dfn[e2[i].to]);
- }
- if(dfn[now]==low[now])
- {
- id[now]=++num;
- while(sta[top]!=now){id[sta[top]]=num;--top;}
- top--;
- }
- }
- int main()
- {
- r(n),r(m),r(X);
- for(re int i=1;i<=m;++i)
- r(u),r(to),add(u,to,1);
- for(re int i=1;i<=n;++i)
- if(!dfn[i])
- tarjan(i);
- for(re int i=1;i<=n;++i)
- w[id[i]]++;
- cnt=0;
- for(re int i=1;i<=n;++i)
- for(re int j=h2[i];j;j=e2[j].nex)
- {
- int y=id[e2[j].to],x=id[i];
- if(x!=y) add(x,y,2),du[y]++;
- }
- for(re int i=1;i<=num;++i)
- if(!du[i]) sta[++top]=i,dp[i]=w[i],ans2[i]=1;
- for(re int i=1;i<=top;++i)
- {
- int x=sta[i];
- for(re int j=h[x];j;j=e[j].nex)
- {
- du[e[j].to]--;
- if(du[e[j].to]==0) sta[++top]=e[j].to;
- if(book[e[j].to]) continue;
- book[e[j].to]=1,sta2[++heap]=e[j].to;
- if(dp[e[j].to]<dp[x]+w[e[j].to])
- dp[e[j].to]=dp[x]+w[e[j].to],ans2[e[j].to]=0;
- if(dp[e[j].to]==dp[x]+w[e[j].to])
- ans2[e[j].to]=(ans2[e[j].to]+ans2[x])%X;
- }
- while(heap){book[sta2[heap]]=0;heap--;}
- ans=MAX(ans,dp[x]);
- }
- ll anse=0;
- for(int i=1;i<=num;++i)
- if(dp[i]==ans) anse=(anse+ans2[i])%X;
- printf("%d\n%lld",ans,anse);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3076057.html