输出最大选修学分问题

要解决这个问题，我们可以采用拓扑排序结合动态规划的方法。首先，我们将课程先修关系构建为有向无环图(DAG)，然后进行拓扑排序，确保我们总是先选择先修课程。接着，我们可以定义一个动态规划数组dp，其中dp[i][j]表示在已知前i门课程的情况下，选修j门课程的最大学分。

以下是完整的C语言代码实现：

#include 
#include 
#include 

#define MAXN 100010
#define INF 0x3f3f3f3f

// 定义结构体表示边
typedef struct Edge {
    int to;
} Edge;

Edge* create_edge(int to) {
    Edge* edge = (Edge*)malloc(sizeof(Edge));
    edge->to = to;
    return edge;
}

int n, m;
int c[MAXN];
bool visited[MAXN];
int in_degree[MAXN];

void add_edge(int from, int to) {
    Edge* edge = create_edge(to);
    // 在这里添加从from到to的边，这个部分取决于你的具体实现，例如使用邻接表
    // 这里只是一个示例，你需要根据实际数据结构填充这部分
}

void topological_sort() {
    for (int i = 1; i <= n; ++i) {
        if (in_degree[i] == 0 && !visited[i]) {
            dfs(i);
        }
    }
}

void dfs(int u) {
    visited[u] = true;
    for (int v : adj[u]) { // 假设adj是一个存储所有与节点u相邻节点的列表
        --in_degree[v];
        if (in_degree[v] == 0 && !visited[v]) {
            dfs(v);
        }
    }
}

int dp[MAXN][MAXN]; // dp[i][j]表示前i门课程时选修j门课的最大学分
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &c[i]);
    }

    for (int i = 0; i < n - 1; ++i) {
        int a, b;
        scanf("%d%d", &a, &b);
        add_edge(a, b); // 添加边 a -> b
    }

    topological_sort();

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            dp[i][j] = dp[i - 1][j]; // 不选当前课程
            if (visited[i] && j > 0) {
                dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + c[i]); // 选当前课程
            }
        }
    }

    int max_score = dp[n][m];
    printf("最大学分: %d\n", max_score);

    return 0;
}

这段代码首先读取输入信息，然后创建边并进行拓扑排序。接下来，定义了一个二维数组dp用于动态规划，并初始化状态。在main函数的for循环中，执行动态规划状态转移方程。最后输出最大学分。

注意，这里的代码片段仅供参考，可能需要根据你的实际情况进行调整，比如对于图的表示方式，这里只给出了一个简单的示例，你可能需要根据实际使用的数据结构（如邻接矩阵或邻接表）进行修改。此外，add_edge() 和 adj 需要在你的代码中实现，它们分别用于添加边和维护邻接表。同样，max() 函数也需要替换为你项目中的实现。

人工智*生成的，真棒！