垂直门户网站有哪些,seo人员的相关薪资,视频网站用虚拟主机,烟台网站建设找三硕科技题解#xff1a;ABC317C - Remembering the Days
题目
链接#xff1a;Atcoder。
链接#xff1a;洛谷。
难度
算法难度#xff1a;B。
思维难度#xff1a;B。
调码难度#xff1a;C。
综合评价#xff1a;普及-。
算法
深度优先搜索。
思路
先建图#x…题解ABC317C - Remembering the Days
·题目
链接Atcoder。
链接洛谷。
·难度
算法难度B。
思维难度B。
调码难度C。
综合评价普及-。
·算法
深度优先搜索。
·思路
先建图在枚举路径起点用dfs遍历出每种选取方法找出边权和最大的一种
·代价
无论如何n小于等于10是肯定够了。
·细节
每个边的信息可以用一维数组套vector掏pair存储代码里能看到。
·代码
#includebits/stdc.h
#define N 11
using namespace std;
vectorpairint,intedge[N]{};
//存储图的信息
int ans0,m0,n0,s0;
//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 i1;im;i){int a0,b0,c0;scanf(%d%d%d,a,b,c);edge[a].push_back({b,c});edge[b].push_back({a,c});}//输入abc并建图for(int i1;in;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){ansmax(ans,s);//在任何一个节点都可以试图更新答案for(pairint,inti:edge[node]){//遍历node所对应的每条边if(b[i.first]false){//原来没有出现过的可以试图向下搜索b[i.first]true;//记录经过si.second;//更新边权和dfs(d1,i.first);//下一层dfs入口b[i.first]false;s-i.second;//回溯}}return;
}
·注意
①由于是无向图连边时一定A-B和B-A都连接。
②回溯。
