【2018/09/08测试T3】【WOJ 3933】观光旅行
程序员文章站
2023-12-26 13:49:03
...
【题目】
【分析】
这道题和我之前写过的一道题比较像戳这里看题
不同点是:1、道路改成双向的了;2、题目要求出方案数
虽说有这样的不同,但是思路还是一样的,我就不赘述了,具体看代码吧
【代码】
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 50005
#define M 200005
#define mod 1000000007
using namespace std;
struct edge
{
int u,v,w;
}a[M];
int f[N],g[N],tf[N],tg[N];
bool comp(const edge &p,const edge &q)
{
return p.w<q.w;
}
int main()
{
int n,m,i,j,last=0;
scanf("%d%d",&n,&m);
for(i=1;i<=m;++i)
scanf("%d%d%d",&a[i].u,&a[i].v,&a[i].w);
sort(a+1,a+m+1,comp);
fill(g+1,g+n+1,1);
int ans=0,res=0;
for(i=1;i<=m;++i)
{
if(a[i].w!=a[i+1].w||i==m)
{
for(j=last+1;j<=i;++j)
{
tf[a[j].u]=f[a[j].u];tg[a[j].u]=g[a[j].u];
tf[a[j].v]=f[a[j].v];tg[a[j].v]=g[a[j].v];
}
for(j=last+1;j<=i;++j)
{
if(tf[a[j].u]+1>f[a[j].v])
f[a[j].v]=tf[a[j].u]+1,g[a[j].v]=tg[a[j].u];
else if(tf[a[j].u]+1==f[a[j].v])
g[a[j].v]=(g[a[j].v]+tg[a[j].u])%mod;
if(tf[a[j].v]+1>f[a[j].u])
f[a[j].u]=tf[a[j].v]+1,g[a[j].u]=tg[a[j].v];
else if(tf[a[j].v]+1==f[a[j].u])
g[a[j].u]=(g[a[j].u]+tg[a[j].v])%mod;
ans=max(ans,max(f[a[j].u],f[a[j].v]));
}
last=i;
}
}
printf("%d\n",ans);
for(i=1;i<=n;++i)
if(f[i]==ans)
res=(res+g[i])%mod;
printf("%d",res);
return 0;
}