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

【2018/09/08测试T3】【WOJ 3933】观光旅行

程序员文章站 2023-12-26 13:49:03
...

【题目】

【2018/09/08测试T3】【WOJ 3933】观光旅行

【2018/09/08测试T3】【WOJ 3933】观光旅行

【2018/09/08测试T3】【WOJ 3933】观光旅行

 

【分析】

这道题和我之前写过的一道题比较像戳这里看题

不同点是: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;
}

 

相关标签: 动态规划(DP)

上一篇:

下一篇: