欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

2018.09.08 NOIP模拟trip(最长链计数)

程序员文章站 2022-03-05 14:50:09
...

2018.09.08 NOIP模拟trip(最长链计数)
2018.09.08 NOIP模拟trip(最长链计数)
2018.09.08 NOIP模拟trip(最长链计数)


差不多是原题啊。
求最长链变成了最长链计数,其余没有变化。
这一次考试为了保险起见本蒟蒻还是写了上次没写的辅助数组。
代码:

#include<bits/stdc++.h>
#define N 50005
#define M 200005
#define mod 1000000007
#define ll long long
using namespace std;
inline int read(){
    int ans=0;
    char ch=getchar();
    while(!isdigit(ch))ch=getchar();
    while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
    return ans;
}
int f[N],n,m,f1[N],hd,tl,maxn=0;
ll g[N],g1[N],ans=0;
struct edge{int u,v,w;}e[M<<1];
inline bool cmp(edge a,edge b){return a.w>b.w;}
int main(){
    freopen("trip.in","r",stdin);
    freopen("trip.out","w",stdout);
    n=read(),m=read(),hd=tl=1;
    for(int i=1;i<=n;++i)f[i]=1,g[i]=1;
    for(int i=1;i<=m;++i)e[i].u=e[i+m].v=read(),e[i].v=e[i+m].u=read(),e[i].w=e[i+m].w=read();
    m<<=1;
    sort(e+1,e+m+1,cmp);
    for(int i=1;i<=m;++i){
        while(e[i].w==e[i+1].w)++i,++tl;
        for(int j=hd;j<=tl;++j)f1[e[j].u]=f[e[j].u],g1[e[j].u]=g[e[j].u];
        for(int j=hd;j<=tl;++j){
            int len=f1[e[j].u]+1;
            if(len>f[e[j].v]){f[e[j].v]=len,g[e[j].v]=g1[e[j].u];}
            else if(len==f[e[j].v])(g[e[j].v]+=g1[e[j].u])%=mod;
        }
        hd=tl+1,tl=hd;
    }
    for(int i=1;i<=n;++i){
        if(f[i]>maxn)maxn=f[i],ans=g[i];
        else if(f[i]==maxn)(ans+=g[i])%=mod;
    }
    cout<<maxn-1<<'\n'<<ans;
    return 0;
}
相关标签: 贪心