526互联

AtCoder Beginner Contest 317 C - Remembering the Days

发布时间 2023-09-01 18:23:07作者: 无上大宗师

C - Remembering the Days


原题链接

题意：每个点最多经过一次，求最长路

思路：数据范围很小，深搜每个点能到其他点的所有路，取最大


#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int g[N][N];
int n,m;
bool st[N];
int w=0;
int ans=0;
void dfs(int u)
{
	st[u]=true;
	for(int i=1;i<=n;i++)
	{
		if(!st[i]&&g[u][i])
		{
			w+=g[u][i];
			st[i]=true;
			dfs(i);
			w-=g[u][i];
			st[i]=false;
		}
	}
	ans=max(ans,w);
}
int main()
{
	cin>>n>>m;
	while(m--)
	{
		int a,b,c;
		cin>>a>>b>>c;
	    g[a][b]=g[b][a]=max(g[a][b],c);
	}
	for(int i=1;i<=n;i++)
	{
		memset(st,0,sizeof(st));
		w=0;
		dfs(i);
		ans=max(w,ans);
	}
	cout<<ans<<'\n';
	
}