您好，请问有人能解答一下这道本科的编程问题吗？谢谢

Question

完整题目在图上，这是一道本科在读的lab的问题。太难了有点不会，刚学c++一年多。

Answer 1

#include <iostream>
#include <cstring>
using namespace std;

int* addtown(int * seed, int x, int* path, int pathn)
{
    int canadd = 0;
    for (int i = 0; i < pathn; i++)
    {
        for (int j = 1; j <= seed[0]; j++)
        {
            if (path[i*2] == seed[j] && path[i*2+1] == x)
            {   canadd = 1; break;  }
            if (path[i*2+1] == seed[j] && path[i*2] == x)
            {   canadd = 1; break;  }           
        }
        if (canadd) break;
    }
    if  (!canadd) return NULL;
    int *p = new int[seed[0] + 2];
    memcpy(p, seed, sizeof(int) * (seed[0] + 1));
    p[0]++;
    p[p[0] - 1] = x;
}

int profit(int * seed)
{
    if (seed[0] == 1) return 0;
    int max, min;
    max = min = seed[1];
    for (int i = 2; i <= seed[0]; i++)
    {
        if (max < seed[i]) max = seed[i];
        if (min > seed[i]) min = seed[i];
    }
    return max - min;
}

int notin(int ** seed, int seedn, int x)
{
    for (int i = 0; i < seedn; i++)
    {
        for (int j = 1; j <= seed[i][0]; j++)
            if (seed[i][j] == x) return 0;
    }
    return 1;
}

int solve(int ** seed, int selectedn, int n, int mn, int* routes)
{
    if (selectedn == n)
    {
        int sum = 0;
        for (int i = 0; i < mn; i++)
        {
            sum += profit(seed[i]);
        }
        return sum;
    }
    int max = -1;
    for (int i = 0; i < n; i++)
    {
        if (notin(seed, mn, i))
        {
            for (int j = 0; j < mn; j++)
            {
                int * seed1 = addtown(seed[j], i, routes, n - 1);
                if (seed1)
                {
                    int maxsub = solve(seed, selectedn + 1, n, mn, routes);
                    if (max < maxsub) max = maxsub;
                }
            }
        }
    }
    return max;
}

int main() {
    int townsn;
    cin >> townsn;
    int* towns = new int[townsn];
    for (int i = 0; i < townsn; i++)
        cin >> towns[i];
    int* routes = new int[(townsn - 1) * 2];
    for (int i = 0; i < townsn - 1; i++)
    {
        int x, y;
        cin >> x >> y;
        routes[i*2] = x - 1;
        routes[i*2+1] = y - 1;
    }
    int k;
    cin >> k;
    int* mchs = new int[k];
    int ** seed = new int*[k];
    for (int i = 0; i < k; i++)
    {
        int x;
        cin >> x;
        mchs[i] = x - 1;
        seed[i] = new int[2];
        seed[i][0] = 1;
        seed[i][1] = x - 1;
    }
    int result = solve(seed, k, townsn, k, routes);
    cout << result << endl;
    return 0;
}

12
3 1 2 3 5 6 7 2 2 4 10 11
1 2
1 3
4 2
5 2
3 6
6 7
6 8
6 9
8 10
9 11
9 12
5
3 8 4 11 12

12

https://ideone.com/B5Btca