P1294 高手去散步()

#include<bits/stdc++.h>
using namespace std;
int n,m; 
int mp[25][55];
bool vis[25];
int ans,s;
 
void dfs(int x,int y){//搜索 ,x,y是这两个景点 
    if(vis[y]){//当我们发现这个景点来过时,我们就可以存下答案了 
        jie:
        ans=max(ans,s);    //只存最大的路程 
        return ;//回到上一步看看有没有更优解 
    }
    for(int i=1;i<=n;i++){//遍历数组 
        if(!vis[x]&&mp[y][i]!=0){//如果这个景点我们没有来过,且我们找到了与之联通的点 
            s+=mp[x][y];        //暂存变量s先存下我们走过的路程 
            vis[x]=1;           //标记我们来过这个景点 
            dfs(y,i);          //进行递归,将下个联通点存入 
            s-=mp[x][y];
            vis[x]=0;        //回溯 
        }
    }
    for(int i=1;i<=n;i++){//这一部分是针对绝路的,就是这个景点只有一个景点与之相连,到了死路不能往下再走了 
        if(mp[y][i]!=0)    //如果发现不是死路就跳出 
        break;
        else if(i==n){    //遍历完地图发现是死路,s就加上当前走过的路程 
            s+=mp[x][y];
            goto jie;    //直接跳入到 ans的判断中 
        }
    }
}

int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){//将景点与景点之间的距离用一个数组去存 
        int a,b;
        cin>>a>>b;
        cin>>mp[a][b];
        mp[b][a]=mp[a][b];
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(mp[i][j]!=0){//如果这个数组不为空就去搜索 
                dfs(i,j);
                memset(vis,0,sizeof(vis));//清空标记 
                s=0;//将暂存变量S清零 
            }
        }
    }
    cout<<ans;
    return 0;
}
#include <cstdio>
#include <iostream>
using namespace std;
const int N =55;
int head[N << 1], cnt, n, m, ans, sum;
bool vis[N];
struct node{
    int nxt, to, w;
}e[N];
int read() {
    int s = 0, w = 1;
    char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-') w = -1;ch = getchar();}
    while(isdigit(ch)) {s = s * 10 + ch - '0';ch = getchar();}
    return s * w;
}
void add(int x, int y, int z) {
    e[++cnt].nxt = head[x];
    e[cnt].to = y;
    e[cnt].w = z;
    head[x] = cnt;
}
void dfs(int x) {
    for(int i = head[x]; i; i = e[i].nxt) 
        if(!vis[e[i].to]) {
            vis[e[i].to] = 1;
            ans += e[i].w;
            sum = max(sum, ans);
            dfs(e[i].to);
            ans -= e[i].w;
            vis[e[i].to] = 0;
        }
}
int main() {
    n = read(), m = read();
    while(m--) {
        int x, y, z;
        x = read(), y = read(), z = read();
        add(x, y, z), add(y, x, z);
    }
    for(int i = 1; i <= n; i++) vis[i] = 1, dfs(i), vis[i] = 0;
    printf("%d\n", sum);
    return 0;
}
————————
#include<bits/stdc++.h>
using namespace std;
int n,m; 
int mp[25][55];
bool vis[25];
int ans,s;
 
void dfs(int x,int y){//搜索 ,x,y是这两个景点 
    if(vis[y]){//当我们发现这个景点来过时,我们就可以存下答案了 
        jie:
        ans=max(ans,s);    //只存最大的路程 
        return ;//回到上一步看看有没有更优解 
    }
    for(int i=1;i<=n;i++){//遍历数组 
        if(!vis[x]&&mp[y][i]!=0){//如果这个景点我们没有来过,且我们找到了与之联通的点 
            s+=mp[x][y];        //暂存变量s先存下我们走过的路程 
            vis[x]=1;           //标记我们来过这个景点 
            dfs(y,i);          //进行递归,将下个联通点存入 
            s-=mp[x][y];
            vis[x]=0;        //回溯 
        }
    }
    for(int i=1;i<=n;i++){//这一部分是针对绝路的,就是这个景点只有一个景点与之相连,到了死路不能往下再走了 
        if(mp[y][i]!=0)    //如果发现不是死路就跳出 
        break;
        else if(i==n){    //遍历完地图发现是死路,s就加上当前走过的路程 
            s+=mp[x][y];
            goto jie;    //直接跳入到 ans的判断中 
        }
    }
}

int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){//将景点与景点之间的距离用一个数组去存 
        int a,b;
        cin>>a>>b;
        cin>>mp[a][b];
        mp[b][a]=mp[a][b];
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(mp[i][j]!=0){//如果这个数组不为空就去搜索 
                dfs(i,j);
                memset(vis,0,sizeof(vis));//清空标记 
                s=0;//将暂存变量S清零 
            }
        }
    }
    cout<<ans;
    return 0;
}
#include <cstdio>
#include <iostream>
using namespace std;
const int N =55;
int head[N << 1], cnt, n, m, ans, sum;
bool vis[N];
struct node{
    int nxt, to, w;
}e[N];
int read() {
    int s = 0, w = 1;
    char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-') w = -1;ch = getchar();}
    while(isdigit(ch)) {s = s * 10 + ch - '0';ch = getchar();}
    return s * w;
}
void add(int x, int y, int z) {
    e[++cnt].nxt = head[x];
    e[cnt].to = y;
    e[cnt].w = z;
    head[x] = cnt;
}
void dfs(int x) {
    for(int i = head[x]; i; i = e[i].nxt) 
        if(!vis[e[i].to]) {
            vis[e[i].to] = 1;
            ans += e[i].w;
            sum = max(sum, ans);
            dfs(e[i].to);
            ans -= e[i].w;
            vis[e[i].to] = 0;
        }
}
int main() {
    n = read(), m = read();
    while(m--) {
        int x, y, z;
        x = read(), y = read(), z = read();
        add(x, y, z), add(y, x, z);
    }
    for(int i = 1; i <= n; i++) vis[i] = 1, dfs(i), vis[i] = 0;
    printf("%d\n", sum);
    return 0;
}