水题ing

结点选择

题目描述

有一棵 n 个节点的树,树上每个节点都有一个正整数权值。如果一个点被选择了,那么在树上和它相邻的点都不能被选择。求选出的点的权值和最大是多少?

数据规模与约定

对于20%的数据, n <= 20。

对于50%的数据, n <= 1000。

对于100%的数据, n <= 100000。

权值均为不超过1000的正整数。

输入

第一行包含一个整数 n 。

接下来的一行包含 n 个正整数,第 i 个正整数代表点 i 的权值。

接下来一共 n-1 行,每行描述树上的一条边。

输出

输出一个整数,代表选出的点的权值和的最大值

样例说明
选择3、4、5号点,权值和为 3+4+5 = 12 。

样例输入

5
1 2 3 4 5
1 2
1 3
2 4
2 5

样例输出

12

思路

这题乍一看是一道关于树的搜索的题目,但是看到数据后就放弃了(;´д`)ゞ,然后想到动态规划,但是想不出来要怎么找状态。后面百度才知道这是一题树形DP,???。什么是树形DP,没有学过。
花了点时间学习了一下,差不多理解这题了。

假设 dp[i][1] 表示选择了 i 节点后的权值,dp[i][0]表示不选 i 节点的权值,那么
dp[i][1] += dp[j][0] --> j 表示 i 节点的孩子
dp[i][0] += max(dp[j][0], dp[j][1]) --> j 表示 i 节点的孩子
最后最大权值为 max(dp[1][0], dp[1][1])

代码

java写的不会过,C++写的过了,不知道为啥

import java.io.*;
import java.util.*;

public class Main {
    static class Reader {
        static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        static StringTokenizer tokenizer = new StringTokenizer("");

        static String nextLine() throws IOException {
            return reader.readLine();
        }

        static String next() throws IOException {
            while (!tokenizer.hasMoreTokens()) {
                tokenizer = new StringTokenizer(reader.readLine());
            }
            return tokenizer.nextToken();
        }

        static int nextInt() throws IOException {
            return Integer.parseInt(next());
        }

        static double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }

        static void close() throws IOException {
            reader.close();
        }
    }

    public static void main(String[] args) throws IOException {
        PrintWriter out = new PrintWriter(new PrintStream(System.out));
        int n = Reader.nextInt();
        int[][] dp = new int[100005][2];
        for (int i = 1; i <= n; i++) {
            dp[i][1] = Reader.nextInt();
        }
        ArrayList<Integer>[] nodes = new ArrayList[100005];
        for (int i = 0; i <= n; i++) {
            nodes[i] = new ArrayList<Integer>();
        }
        for (int i = 0; i < n - 1; i++) {
            int v = Reader.nextInt();
            int e = Reader.nextInt();
            nodes[v].add(e);
            nodes[e].add(v);
        }
        dfs(1, -1, nodes, dp);
        out.println(Math.max(dp[1][1], dp[1][0]));
        out.flush();
    }

    static void dfs(int x, int pre, List<Integer> []nodes, int[][] dp) {
        for (int i = 0; i < nodes[x].size(); i++) {
            int e = nodes[x].get(i);
            if (e == pre) continue;
            dfs(e, x, nodes, dp);
            dp[x][1] += dp[e][0];
            dp[x][0] += Math.max(dp[e][0], dp[e][1]);
        }
    }
}
#include<iostream>
#include<vector>
#include<string.h>
#define MAXN 100005
using namespace std;
vector<int> nodes[MAXN];
int dp[MAXN][2];
int n, v, e;
void dfs(int x, int pre) {
    for (int i = 0; i < nodes[x].size(); i++) {
        int s = nodes[x][i];
        if (s == pre) continue;
        dfs(s, x);
        dp[x][1] += dp[s][0];
        dp[x][0] += max(dp[s][0], dp[s][1]);
    }
}
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> dp[i][1];
    }
    for (int i = 0; i < n - 1; i++) {
        cin >> v >> e;
        nodes[v].push_back(e);
        nodes[e].push_back(v);
    }
    dfs(1, 0);
    cout << max(dp[1][0], dp[1][1]);
    return 0;
}

网络寻路

题目描述

X 国的一个网络使用若干条线路连接若干个节点。节点间的通信是双向的。某重要数据包,为了安全起见,必须恰好被转发两次到达目的地。该包可能在任意一个节点产生,我们需要知道该网络中一共有多少种不同的转发路径。
源地址和目标地址可以相同,但中间节点必须不同。

如下图所示的网络。
1 -> 2 -> 3 -> 1 是允许的
1 -> 2 -> 1 -> 2 或者 1 -> 2 -> 3 -> 2 都是非法的。

输入

输入数据的第一行为两个整数N M,分别表示节点个数和连接线路的条数(1<=N<=10000; 0<=M<=100000)。
接下去有M行,每行为两个整数 u 和 v,表示节点u 和 v 联通(1<=u,v<=N , u!=v)。
输入数据保证任意两点最多只有一条边连接,并且没有自己连自己的边,即不存在重边和自环。

输出

输出一个整数,表示满足要求的路径条数。

样例输入

3 3
1 2
2 3
1 3

样例输出

6

思路

这题简单没啥好说的了

代码

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;
 
public class Main {
    static class Reader {
        static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        static StringTokenizer tokenizer = new StringTokenizer("");
 
        static String nextLine() throws IOException {
            return reader.readLine();
        }
 
        static String next() throws IOException {
            while (!tokenizer.hasMoreTokens()) {
                tokenizer = new StringTokenizer(reader.readLine());
            }
            return tokenizer.nextToken();
        }
 
        static int nextInt() throws IOException {
            return Integer.parseInt(next());
        }
 
        static double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }
 
        static void close() throws IOException {
            reader.close();
        }
    }
 
    public static void main(String[] args) throws IOException {
        PrintWriter out = new PrintWriter(new PrintStream(System.out));
        int n = Reader.nextInt();
        int m = Reader.nextInt();
        Solution s = new Solution(n);
        for (int i = 0; i < m; i++) {
            s.addEdge(Reader.nextInt(), Reader.nextInt());
        }
        out.println(s.dfs());
        out.flush();
    }
}
class Solution {
    private final int MAX_L = 10005;
    private int n, ans;
    private List<Integer> []map;
    private int []vis;
 
    public Solution(int n) {
        this.n = n;
        this.map = new ArrayList[MAX_L];
        for (int i = 1; i <= n; i++) {
            map[i] = new ArrayList<Integer>();
        }
        this.vis = new int[MAX_L];
    }
 
    public void addEdge(int v, int e) {
        map[v].add(e);
        map[e].add(v);
    }
 
    public int dfs() {
        for (int i = 1; i <= n; i++) {
            dfs(i, -1, 0);
        }
        return ans;
    }
 
    private void dfs(int cur, int cnt, int sum) {
        if (sum == 3) {
            ans++;
            return;
        }
        for (int i = 0; i < map[cur].size(); i++) {
            int e = map[cur].get(i);
            if (e != cnt) dfs(e, cur, sum + 1);
        }
    }
}

数的划分

题目描述

将整数n分成k份,且每份不能为空,任意两份不能相同(不考虑顺序)。
例如:n=7,k=3,下面三种分法被认为是相同的。
1,1,5;
1,5,1;
5,1,1;
问有多少种不同的分法。
输入:n,k ( 6 < n ≤ 200,2 ≤ k ≤ 6 )
输出:一个整数,即不同的分法。

输入

两个整数 n,k ( 6 < n ≤ 200, 2 ≤ k ≤ 6 )

输出

1个整数,即不同的分法。

样例输入

7 3 

样例输出

4

AC代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

/**
 * @author : lwj
 * createTime  : 2020/1/23 13:40
 * description : Reprint please indicate the source
 */
public class Main {
    static class Reader {
        static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        static StringTokenizer tokenizer = new StringTokenizer("");
        static String nextLine() throws IOException {
            return reader.readLine();
        }
        static String next() throws IOException {
            while (!tokenizer.hasMoreTokens()) {
                tokenizer = new StringTokenizer(reader.readLine());
            }
            return tokenizer.nextToken();
        }

        static int nextInt() throws IOException {
            return Integer.parseInt(next());
        }

        static double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }
        static void close() throws IOException {
            reader.close();
        }
    }

    public static void main(String[] args) throws IOException {
        int n = Reader.nextInt();
        int k = Reader.nextInt();
        Code_2 code_2 = new Code_2(n, k);
        code_2.dfs();
    }
}
class Code_2 {
    private int ans, n, k;

    public Code_2(int n, int k) {
        this.n = n;
        this.k = k;
    }

    public void dfs() {
        this.dfs(0, 0, 1);
        System.out.println(ans);
    }

    private void dfs(int sum, int cnt, int cur) {
        if(sum == n && cnt == k) {
            ans++;
            return;
        }
        if(cnt >= k) {
            return;
        }
        for (int i = cur; i <= n - cur; i++) {
            if(sum + i > n) return;
            dfs(sum + i, cnt + 1, i);
        }
    }
}

#include<stdio.h>
int n, k, ans;
void dfs(int index, int ct, int cnt) {
    int i = 0;
    if(ct == n && cnt == k) {
        ans++;
    }
    if(cnt >= k) {
        return;
    }
    for(i = index; i <= n - ct; i++) {
        if(ct + i > n) {
            continue;
        }
        dfs(i, i + ct, cnt + 1);
    }
}
int main() {
    scanf("%d %d", &n, &k);
    dfs(1, 0, 0);
    printf("%d\n", ans);
    return 0;
}


危险系数

题目描述

问题描述
抗日战争时期,冀中平原的地道战曾发挥重要作用。
地道的多个站点间有通道连接,形成了庞大的网络。但也有隐患,当敌人发现了某个站点后,其它站点间可能因此会失去联系。
我们来定义一个危险系数DF(x,y):
对于两个站点x和y (x != y), 如果能找到一个站点z,当z被敌人破坏后,x和y不连通,那么我们称z为关于x,y的关键点。相应的,对于任意一对站点x和y,危险系数DF(x,y)就表示为这两点之间的关键点个数。
本题的任务是:已知网络结构,求两站点之间的危险系数。

输入

输入数据第一行包含2个整数n(2 < = n < = 1000), m(0 < = m < = 2000),分别代表站点数,通道数;
接下来m行,每行两个整数 u,v (1 < = u, v < = n; u != v)代表一条通道;
最后1行,两个数u,v,代表询问两点之间的危险系数DF(u, v)。

输出

一个整数,如果询问的两点不连通则输出-1.

样例输入

7  6 
1  3 
2  3 
3  4 
3  5 
4  5 
5  6 
1  6  

样例输出

2

思路

主要思路就是去除某个顶点e(e != u && e != v) 后,判断去除e点后,u和v是否还是连通的,如果不连通的话,计数器加一
至于怎么判断连通性,......直接深搜

AC代码

#include<iostream>
#include<string.h>
using namespace std;
int map[1005][1005];
int mp[1005];
int n, m, a, b, ans;
bool f = false;
void dfs(int cur, int p) {
    if (cur == b) {
        f = true;
        return;
    }
    if (f) return;
    for (int i = 1; i <= n; i++) {
        if (map[cur][i] == 1 && i != p && mp[i] == 0) {
            mp[i] = 1;
            dfs(i, p);
        }
    }
}
int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> a >> b;
        map[a][b] = 1;
        map[b][a] = 1;
    }
    cin >> a >> b;
    for (int i = 1; i <= n; i++) {
        if (i != a && i != b) {
            memset(mp, 0, sizeof(mp));
            f = false;
            mp[a] = 1;
            dfs(a, i);
            if (!f) {
                ans++;
            }
        }
    }
    cout << ans << endl;
    return 0;
}
import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;
 
public class Main {
    static class Reader {
        static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        static StringTokenizer tokenizer = new StringTokenizer("");
 
        static String nextLine() throws IOException {
            return reader.readLine();
        }
 
        static String next() throws IOException {
            while (!tokenizer.hasMoreTokens()) {
                tokenizer = new StringTokenizer(reader.readLine());
            }
            return tokenizer.nextToken();
        }
 
        static int nextInt() throws IOException {
            return Integer.parseInt(next());
        }
 
        static double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }
 
        static void close() throws IOException {
            reader.close();
        }
    }
 
    public static void main(String[] args) throws IOException {
        PrintWriter out = new PrintWriter(new PrintStream(System.out));
        int n = Reader.nextInt();
        int m = Reader.nextInt();
        Solution s = new Solution(n);
        for (int i = 0; i < m; i++) {
            s.addEdge(Reader.nextInt(), Reader.nextInt());
        }
        out.println(s.dfs(Reader.nextInt(), Reader.nextInt()));
        out.flush();
    }
}
class Solution {
    private final int MAX_L = 1005;
    private int n, ans, flag;
    private List<Integer> []map;
    private int []vis;
 
    public Solution(int n) {
        this.n = n;
        this.flag = 0;
        this.map = new ArrayList[MAX_L];
        for (int i = 1; i <= n; i++) {
            map[i] = new ArrayList<Integer>();
        }
        this.vis = new int[MAX_L];
    }
 
    public void addEdge(int v, int e) {
        map[v].add(e);
        map[e].add(v);
    }
 
    public int dfs(int u, int v) {
        for (int i = 1; i <= n; i++) {
            if (i != u && i != v) {
                vis[u] = 1;
                dfs(u, v, i);
                if (flag == 0) ans++;
                Arrays.fill(vis, 0);
                flag = 0;
            }
        }
        return ans;
    }
 
    private void dfs(int cur, int end, int cnt) {
        if (cur == end) {
            flag = 1;
            return;
        }
        if (flag == 0) {
            for (int i = 0; i < map[cur].size(); i++) {
                int e = map[cur].get(i);
                if (e != cnt && vis[e] == 0) {
                    vis[e] = 1;
                    dfs(e, end, cnt);
                }
            }
        }
    }
}

剪格子

题目描述

如下图所示,3 x 3 的格子中填写了一些整数。
234123541325
我们沿着图中的星号线剪开,得到两个部分,每个部分的数字和都是60。
本题的要求就是请你编程判定:对给定的m x n 的格子中的整数,是否可以分割为两个部分,使得这两个区域的数字和相等。
如果存在多种解答,请输出包含左上角格子的那个区域包含的格子的最小数目。
如果无法分割,则输出 0。

输入

程序先读入两个整数 m n 用空格分割 (m,n< 10)。
表示表格的宽度和高度。
接下来是n行,每行m个正整数,用空格分开。每个整数不大于10000。

输出

输出一个整数,表示在所有解中,包含左上角的分割区可能包含的最小的格子数目。

样例输入

3  3 
10  1  52 
20  30  1 
1  2  3 

样例输出

3

思路

  1. 首先先判断矩阵总和是奇数还是偶数,如果是奇数的话直接输出0
  2. 对矩阵每一个点都进行一次深搜,出口就是当sum(当前总和)等于矩阵一半的时候,且包含左上角格子
  3. 搜完一个点之后记得回溯,清楚标记

AC代码

#include<iostream>
#include<string.h>
using namespace std;
int dir[4][2] = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}};
int map[15][15];
int vis[15][15];
int m, n, sum, half, ans = 250;
void dfs(int x, int y, int ac, int step) {
    if (ac == half) {
        if(vis[0][0] == 1) {
            if(ans > step) ans = step;
            return;
        }
    } else if (ac < half) {
        for (int i = 0; i < 4; i++) {
            int nx = x + dir[i][0];
            int ny = y + dir[i][1];
            if(0 <= nx && nx < n && 0 <= ny && ny < m && vis[nx][ny] == 0) {
                vis[nx][ny] = 1;
                dfs(nx, ny, ac + map[nx][ny], step + 1);
                vis[nx][ny] = 0;
            }
        }
    }
}
int main() {
    cin >> m >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> map[i][j];
            sum += map[i][j];
        }
    }
    if(sum % 2 != 0) {
        cout << "0" << endl;
    } else {
        half = sum / 2;
        memset(vis, 0, sizeof(vis));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                vis[i][j] = 1;
                dfs(i, j, map[i][j], 1);
                vis[i][j] = 0;
            }
        }
        if(ans == 250) {
            cout << "0" << endl;
        } else {
            cout << ans << endl;
        }
    }
    return 0;
}

大臣的旅费

题目描述

很久以前,T王国空前繁荣。为了更好地管理国家,王国修建了大量的快速路,用于连接首都和王国内的各大城市。
为节省经费,T国的大臣们经过思考,制定了一套优秀的修建方案,使得任何一个大城市都能从首都直接或者通过其他大城市间接到达。同时,如果不重复经过大城市,从首都到达每个大城市的方案都是唯一的。
J是T国重要大臣,他巡查于各大城市之间,体察民情。所以,从一个城市马不停蹄地到另一个城市成了J最常做的事情。他有一个钱袋,用于存放往来城市间的路费。
聪明的J发现,如果不在某个城市停下来修整,在连续行进过程中,他所花的路费与他已走过的距离有关,在走第x千米到第x+1千米这一千米中(x是整数),他花费的路费是x+10这么多。也就是说走1千米花费11,走2千米要花费23。
J大臣想知道:他从某一个城市出发,中间不休息,到达另一个城市,所有可能花费的路费中最多是多少呢?

输入

输入的第一行包含一个整数n,表示包括首都在内的T王国的城市数
城市从1开始依次编号,1号城市为首都。
接下来n-1行,描述T国的高速路(T国的高速路一定是n-1条)
每行三个整数Pi, Qi, Di,表示城市Pi和城市Qi之间有一条高速路,长度为Di千米。

输出

输出一个整数,表示大臣J最多花费的路费是多少。

样例输入

5 
1  2  2
1  3  1
2  4  5
2  5  4

样例输出

135

思路

  1. 首先从u dfs找到最远点v ,然后从v开始,dfs找到的最远点一定是树的直径

证明:

如果u->v 和树的直径没有公共点,则可以从树的直径终点到u引一条边,树直径变长了,矛盾
假设交点为k,那么k->v (或者就是v本身) 一定是树直径的一部分,(最优子结构)
这样就证明了v一定在树的直径的端点处,(为什么是端点,因为u->v是最远的,一定是叶子节点)
  1. 其实可以直接把每个点都深搜一遍,也能找到最长的一条路径,不过这个方法可能会超时
  2. 还有一点需要注意,由于题目测试数据的原因,不能用邻接矩阵,只能用邻接表

AC代码

#include<iostream>
#include<vector>
#include<string.h>
using namespace std;
struct Edge {
    int v, e, w;
};
vector<Edge> map[10005];
int vis[10005];
int ans, imax = -999999;
int n, p, q, d, point;
void dfs(int start, int sum) {
    vis[start] = 1;
    if(sum > imax) {
        imax = sum;
        point = start;
    }
    for (int i = 0; i < map[start].size(); i++) {
        Edge e = map[start][i];
        if(vis[e.e] == 0) {
            sum += e.w;
            dfs(e.e, sum);
            sum -= e.w;
        }
    }
}
void cal() {
    for(int i = 1; i <= imax; i++) {
        ans += (i + 10);
    }
    cout << ans << endl;
}
int main() {
    cin >> n;
    for (int i = 0; i < n - 1; i++) {
        cin >> p >> q >> d;
        Edge e;
        e.v = p; e.e = q; e.w = d;
        map[p].push_back(e);
        e.v = q; e.e = p;
        map[q].push_back(e);
    }
    dfs(1, 0);
    memset(vis, 0, sizeof(vis));
    dfs(point, 0);
    cal();
    return 0;
}
import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    static class Reader {
        static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        static StringTokenizer tokenizer = new StringTokenizer("");

        static String nextLine() throws IOException {
            return reader.readLine();
        }

        static String next() throws IOException {
            while (!tokenizer.hasMoreTokens()) {
                tokenizer = new StringTokenizer(reader.readLine());
            }
            return tokenizer.nextToken();
        }

        static int nextInt() throws IOException {
            return Integer.parseInt(next());
        }

        static double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }

        static void close() throws IOException {
            reader.close();
        }
    }

    public static void main(String[] args) throws IOException {
        PrintWriter out = new PrintWriter(new PrintStream(System.out));
        int n = Reader.nextInt();
        Solution s = new Solution(n);
        for (int i = 0; i < n - 1; i++) {
            s.addEdge(Reader.nextInt(), Reader.nextInt(), Reader.nextInt());
        }
        out.println(s.dfs());
        out.flush();
    }
}
class Solution {
    static class Edge {
        int v, e, w;
        public Edge(int v, int e, int w) {
            this.v = v;
            this.e = e;
            this.w = w;
        }
    }

    private List<Edge> []map;
    private int V, ans = Integer.MIN_VALUE, cnt;
    private int []vis;

    public Solution(int V) {
        this.V = V;
        this.vis = new int[V + 5];
        this.map = new ArrayList[10005];
        for (int i = 1; i <= V; i++) {
            map[i] = new ArrayList<Edge>();
        }
    }

    public void addEdge(int v, int e, int w) {
        map[v].add(new Edge(v, e, w));
        map[e].add(new Edge(e, v, w));
    }

    public int dfs() {
        dfs(1, 0);
        Arrays.fill(vis, 0);
        dfs(cnt, 0);
        int cs = 0;
        for (int i = 1; i <= ans; i++) {
            cs += (10 + i);
        }
        return cs;
    }

    private void dfs(int cur, int sum) {
        vis[cur] = 1;
        if (sum > ans) {
            ans = sum;
            cnt = cur;
        }
        for (int i = 0; i < map[cur].size(); i++) {
            Edge e = map[cur].get(i);
            if (vis[e.e] == 0) dfs(e.e, sum + e.w);
        }
    }
}



水图

题目描述

小w不会离散数学,所以她van的图论游戏是送分的
小w有一张n个点n-1条边的无向联通图,每个点编号为1~n,每条边都有一个长度
小w现在在点x上
她想知道从点x出发经过每个点至少一次,最少需要走多少路

输入描述:

第一行两个整数 n,x,代表点数,和小w所处的位置
第二到第n行,每行三个整数 u,v,w,表示u和v之间有一条长为w的道路

输出描述:

一个数表示答案

输入

3 1
1 2 1
2 3 1

输出

2

备注:

1 ≤ n ≤ 50000 , 1 ≤ w ≤ 2147483647

思路

从一个结点出发要遍历所有的结点,所以每条路径都要走两次,而只有一条路径只用走一次,所以我们只需要找出最长的一条路径让他只走一次就好了,所以最后的结果就是所有边的权值之和的二倍减去最长的一条路径。

AC代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.StringTokenizer;

/**
 * @author : lwj
 * createTime  : 2020/1/22 13:09
 * description : Reprint please indicate the source
 */
public class Main {
    static class reader {
        static BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
        static StringTokenizer tokenizer = new StringTokenizer("");
        static String nextLine() throws IOException {
            return read.readLine();
        }
        static String next() throws IOException {
            while (!tokenizer.hasMoreTokens()) {
                tokenizer = new StringTokenizer(read.readLine());
            }
            return tokenizer.nextToken();
        }

        static int nextInt() throws IOException {
            return Integer.parseInt(next());
        }

        static double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }
        static void close() throws IOException {
            read.close();
        }
    }

    public static void main(String[] args) throws IOException {
        int n = reader.nextInt();
        int x = reader.nextInt();
        Solution_6 solution_6 = new Solution_6(n);
        for (int i = 0; i < n - 1; i++) {
            solution_6.addEdge(reader.nextInt(), reader.nextInt(), reader.nextInt());
        }
        solution_6.dfs(x);
    }
}

class Solution_6 {

    static class Edge {
        int v, e;
        long w;

        public Edge(int v, int e, long w) {
            this.v = v;
            this.e = e;
            this.w = w;
        }
    }

    private long ans;
    private LinkedList<Edge> []map;
    private int []vis;
    private long sum;

    public Solution_6(int n) {
        this.map = new LinkedList[n + 5];
        this.vis = new int[n + 5];
        for (int i = 1; i <= n; i++) {
            map[i] = new LinkedList<Edge>();
        }
    }

    public void addEdge(int v, int e, long w) {
        sum += w;
        map[v].add(new Edge(v, e, w));
        map[e].add(new Edge(e, v, w));
    }

    public void dfs(int start) {
        this.search(start, 0);
        System.out.println(2 * sum - ans);
    }

    private void search(int cur, long dis) {
        vis[cur] = 1;
        if(map[cur].size() == 1 && vis[map[cur].get(0).e] == 1) {
            ans = Math.max(ans, dis);
            return;
        }
        for (int i = 0; i < map[cur].size(); i++) {
            Edge e = map[cur].get(i);
            if(vis[e.e] == 0) {
                search(e.e, dis + map[cur].get(i).w);
            }
        }
    }
}

本文由 罗罗 创作,如果您觉得本文不错,请随意赞赏
采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外,均为本站原创或翻译,转载前请务必署名
原文链接:https://www.lwjppz.cn /archives/刷题刷题ing
最后更新于:2020-04-09 19:00:55

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×