题解：ABC317C - Remembering the Days

题解：ABC317C - Remembering the Days

·题目

链接：Atcoder。

链接：洛谷。

·难度

算法难度：B。

思维难度：B。

调码难度：C。

综合评价：普及-。

·算法

深度优先搜索。

·思路

先建图，在枚举路径起点，用dfs遍历出每种选取方法，找出边权和最大的一种，

·代价

无论如何n小于等于10是肯定够了。

·细节

每个边的信息可以用一维数组套vector掏pair存储（代码里能看到）。

·代码

#include<bits/stdc++.h>
#define N 11
using namespace std;
vector<pair<int,int>>edge[N]={};
//存储图的信息
int ans=0,m=0,n=0,s=0;
//ans记录答案，s记录dfs过程中经过所有的边权总和
bool b[N]={};
//记录在dfs过程中每个点是否被经过
inline void dfs(int d,int node);
//函数用来搜索每种选择情况，d表示目前经过的总点数，node表示当前节点
int main(){scanf("%d%d",&n,&m);//输入n、mfor(int i=1;i<=m;i++){int a=0,b=0,c=0;scanf("%d%d%d",&a,&b,&c);edge[a].push_back({b,c});edge[b].push_back({a,c});}//输入abc并建图for(int i=1;i<=n;i++){b[i]=true;//记录起点被经过dfs(1,i);//dfs入口b[i]=false;//回溯}//枚举起始点，j进入dfsprintf("%d\n",ans);//输出答案return 0;
}
inline void dfs(int d,int node){ans=max(ans,s);//在任何一个节点，都可以试图更新答案for(pair<int,int>i:edge[node]){//遍历node所对应的每条边if(b[i.first]==false){//原来没有出现过的可以试图向下搜索b[i.first]=true;//记录经过s+=i.second;//更新边权和dfs(d+1,i.first);//下一层dfs入口b[i.first]=false;s-=i.second;//回溯}}return;
}

·注意

①由于是无向图，连边时一定A-B和B-A都连接。

②回溯。