题目分析

有 n 名演员和 m 条“必须严格高于”关系，每条关系是“演员 a 的片酬要高于演员 b”。

• 每位演员基础片酬至少 100 元；
• 调整步长 10 元；
• 在满足所有“严格大于”关系前提下，使总片酬最小。

将演员 i 的实际片酬记为

salary[i] = 100 + 10 * level[i]

其中 level[i] 是非负整数。对于关系 a > b，要保证

100 + 10*level[a] > 100 + 10*level[b]

等价于

level[a] >= level[b] + 1

我们在有向图里加一条 b -> a 的边，就变成在这个 DAG 上求每个节点的最小“层数”（level），再累加即可。

解题思路

1. 建图

• 对每条关系 a > b，加入一条反向边 b -> a；
• 统计每个节点的入度。

2. 拓扑排序 + 环检测

• 用 Kahn 算法：把所有入度为 0 的节点入队，依次出队并将它们的所有出边对应的目标节点入度减 1，新的入度 0 节点继续入队；
• 如果最后处理的节点数 < n，则说明有环，输出 -1。

3. 最长路径 DP

• 初始化 dp[i] = 0；
• 按拓扑序遍历每个节点 u，针对每条边 u -> v，做

  dp[v] = max(dp[v], dp[u] + 1)
  

• 这样 dp[v] 就是 v 的最小 level。

4. 计算答案

• 总片酬 = n*100 + 10 * sum(dp[i])。

四、复杂度分析

• 建图、拓扑排序、DP 都是 O(n + m)
• 空间 O(n + m)
• 满足 n≤10⁴, m≤2×10⁴ 的要求。

代码实现

Python 代码

import sys
from collections import deque

def solve():
    input = sys.stdin.readline
    T = int(input())
    for _ in range(T):
        n, m = map(int, input().split())
        # 构建反向图 b->a
        adj = [[] for _ in range(n+1)]
        indegree = [0]*(n+1)
        for _ in range(m):
            a, b = map(int, input().split())
            adj[b].append(a)
            indegree[a] += 1

        # 拓扑排序
        q = deque(i for i in range(1, n+1) if indegree[i]==0)
        topo = []
        while q:
            u = q.popleft()
            topo.append(u)
            for v in adj[u]:
                indegree[v] -= 1
                if indegree[v] == 0:
                    q.append(v)
        # 如果存在环
        if len(topo) < n:
            print(-1)
            continue

        # DP 最长路径
        dp = [0]*(n+1)
        for u in topo:
            for v in adj[u]:
                if dp[v] < dp[u] + 1:
                    dp[v] = dp[u] + 1

        total = n*100 + 10*sum(dp[1:])
        print(total)

if __name__ == "__main__":
    solve()

Java 代码

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine().trim());
        StringBuilder sb = new StringBuilder();
        while (T-- > 0) {
            String[] parts = br.readLine().split(" ");
            int n = Integer.parseInt(parts[0]);
            int m = Integer.parseInt(parts[1]);
            List<List<Integer>> adj = new ArrayList<>(n+1);
            for (int i = 0; i <= n; i++) adj.add(new ArrayList<>());
            int[] indegree = new int[n+1];

            for (int i = 0; i < m; i++) {
                parts = br.readLine().split(" ");
                int a = Integer.parseInt(parts[0]), b = Integer.parseInt(parts[1]);
                // 反向边 b->a
                adj.get(b).add(a);
                indegree[a]++;
            }

            // 拓扑排序
            Queue<Integer> q = new ArrayDeque<>();
            for (int i = 1; i <= n; i++) {
                if (indegree[i] == 0) q.offer(i);
            }
            List<Integer> topo = new ArrayList<>();
            while (!q.isEmpty()) {
                int u = q.poll();
                topo.add(u);
                for (int v : adj.get(u)) {
                    if (--indegree[v] == 0) q.offer(v);
                }
            }
            if (topo.size() < n) {
                sb.append("-1\n");
                continue;
            }

            // DP 最长路径
            int[] dp = new int[n+1];
            for (int u : topo) {
                for (int v : adj.get(u)) {
                    dp[v] = Math.max(dp[v], dp[u] + 1);
                }
            }
            long sum = 1L * n * 100;
            for (int i = 1; i <= n; i++) sum += 10L * dp[i];
            sb.append(sum).append('\n');
        }
        System.out.print(sb);
    }
}

C++ 代码

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int T;
    cin >> T;
    while(T--){
        int n, m;
        cin >> n >> m;
        vector<vector<int>> adj(n+1);
        vector<int> indegree(n+1, 0);

        for(int i = 0; i < m; i++){
            int a, b;
            cin >> a >> b;
            // 反向边 b->a
            adj[b].push_back(a);
            indegree[a]++;
        }

        // 拓扑排序
        queue<int> q;
        for(int i = 1; i <= n; i++){
            if(indegree[i] == 0) q.push(i);
        }
        vector<int> topo;
        while(!q.empty()){
            int u = q.front(); q.pop();
            topo.push_back(u);
            for(int v : adj[u]){
                if(--indegree[v] == 0)
                    q.push(v);
            }
        }
        if((int)topo.size() < n){
            cout << -1 << "\n";
            continue;
        }

        // DP 最长路径
        vector<int> dp(n+1, 0);
        for(int u : topo){
            for(int v : adj[u]){
                dp[v] = max(dp[v], dp[u] + 1);
            }
        }

        long long ans = 1LL * n * 100;
        for(int i = 1; i <= n; i++){
            ans += 10LL * dp[i];
        }
        cout << ans << "\n";
    }
    return 0;
}

题目内容

多多制作人正在筹拍一部电影，需要招募一批演员。为了确保影片顺利拍摄，制作团队需要合理地分配每位演员的片酬，否则演员可能罢演。片酬的分配由团队成员共同商议决定，每位成员对演员的片酬标准有自己独特的评估意见。在团队讨论时，成员们可能会根据演员所饰演角色的复杂性、表演难度、台词量等因素，提出不同的薪资调整建议，例如，某些成员认为某个角色的表演难度较大，应该给予更高的片酬；而另一些成员则认为某个角色的台词较多，也应该提高该演员的报酬。团队成员的意见可以通过会议提出，并且不同成员的意见有可能存在矛盾，每条意见以一对明确的优先顺序给出，例如，某个演员的片酬应该高于另一个演员的片酬。请你帮多多计算在满足所有制作团队成员的意见下，求出一个使得演员片酬总额最小的方案。每位演员的片酬必须至少为 $100$ 元，且每次调整的增量为 $10$ 元。

输入描述

第一行为一个整数 $T(1\leq T\leq 10)$，表示共有 $T$ 个测试数据。

每组测试数据:

第一行为两个整数 $n(1\leq n\leq 10000)$ 和 $m(1\leq m\leq 20000)$，分别表示招募演员的总数和制作团队成员提出的意见数。

接下来的 $m$ 行:

每行输入两个整数 $a_i,b_i(1\leq a_i,b_i \leq n)$ 表示有制作团队成员认为演员 $a_i$ 的片酬应当比演员 $b_i$ 的片酬高。

输出描述

每组数据输出一个结果，每个结果占一行，如果满足不了所有制作团队成员的意见则输出 $-1$。

补充说明

对于 $20$% 的数据有: $1\leq n\leq 100,1\leq m\leq 200$

对于 $40$% 的数据有: $1\leq n\leq 1000,1\leq m\leq 2000$

对于 $100$% 的数据有: $1\leq n\leq 10000,1\leq m\leq 20000$

示例1

输入

1
7 4
7 2
4 6
2 5
7 5

输出

740

说明

演员 $7$ 片酬需要比 $2,5$ 高

演员 $4$ 片酬需要比 $6$ 高

演员 $2$ 片酬需要比 $5$ 高

因此总额最小的招募方案为:

|演员|演员$1$|演员$2$|演员$3$|演员$4$|演员$5$|演员$6$|演员$7$|

|片酬|$100$|$110$|$100$|$110$|$100$|$100$|$120$|

总计片酬 $740$

示例2

输入

1
3 2
1 3
3 2

输出

330

说明

演员 $1$ 片酬需要比 $3$ 高

演员 $3$ 片酬需要比 $2$ 高

因此总额最小的招募方案为:

|演员|演员$1$|演员$2$|演员$3$|

|片酬|$120$|$100$|$110$|

总计片酬 $330$