64546
346
911
232
260
204
354
770
686
656
180
492
760
332
73
994
129
292
221
732
<1304086 bytes omitted>
用户输出
359028438254
编号 | 题目 | 状态 | 分数 | 总时间 | 内存 | 代码 / 答案文件 | 提交者 | 提交时间 |
---|---|---|---|---|---|---|---|---|
#31655 | #2070. 选课 | Time Limit Exceeded | 0 | 7596 ms | 27740 K | Python 3 / 2.1 K | banned24 | 2025-03-16 19:03:06 |
import sys
sys.setrecursionlimit(200000)
def dfs_iterative(start, adj, credit, dp, visited):
stack = [start]
parent = [-1] * len(adj)
order = []
while stack:
node = stack[-1]
if visited[node] == 0:
visited[node] = 1
order.append(node)
for neighbor in adj[node]:
if visited[neighbor] == 0: # 还没有访问过
parent[neighbor] = node
stack.append(neighbor)
else:
stack.pop()
# 处理DFS结果
for u in reversed(order):
dp[u][0] = 0 # 不选u
dp[u][1] = credit[u] # 选u时的初始学分是该课程的学分
for v in adj[u]:
if v != parent[u]:
dp[u][0] += max(dp[v][0], dp[v][1]) # 如果不选u,则v可以选也可以不选
dp[u][1] += dp[v][0] # 如果选u,则v不能选
def main():
# 读取输入
n = int(input())
credit = [0] * n
for i in range(n):
credit[i] = int(input())
# 邻接表存储图
adj = [[] for _ in range(n)]
# 读取冲突关系并构建图
for i in range(n):
data = list(map(int, input().split()))
Ai = data[0]
for j in range(1, Ai + 1):
adj[i].append(data[j] - 1) # 课程编号从1开始,转换为0-based
adj[data[j] - 1].append(i) # 无向图
# DP数组,dp[u][0]表示不选u时的最大学分,dp[u][1]表示选u时的最大学分
dp = [[0, 0] for _ in range(n)]
visited = [0] * n # 0: 未访问,1: 正在访问,2: 已访问
total_max_credits = 0
# 遍历每个连通分量
for i in range(n):
if visited[i] == 0: # 如果课程i没有被访问过
dfs_iterative(i, adj, credit, dp, visited)
# 对于每个连通分量的根节点,选择dp[u][0]和dp[u][1]中的较大者
total_max_credits += max(dp[i][0], dp[i][1])
print(total_max_credits)
if __name__ == "__main__":
main()
64546
346
911
232
260
204
354
770
686
656
180
492
760
332
73
994
129
292
221
732
<1304086 bytes omitted>
用户输出
359028438254
87763
360
122
644
448
64
834
996
456
514
928
337
622
831
299
150
359
616
816
573
<1785910 bytes omitted>
97101
785
659
469
214
368
744
560
280
670
968
816
272
430
41
500
483
72
216
714
<1980327 bytes omitted>
96463
15
109
882
404
711
196
826
474
68
958
551
512
664
306
99
868
80
392
1000
5
<1967031 bytes omitted>
84245
394
737
934
484
602
32
127
444
543
384
860
925
416
248
896
432
198
964
400
<1712626 bytes omitted>
32637
135
269
88
586
80
410
895
360
898
480
37
686
182
520
877
879
124
167
932
4
<644317 bytes omitted>
用户输出
45082199992
Special Judge 信息
Files user_out and answer differ
系统信息
Exited with return code 0
60741
802
467
361
954
776
84
314
830
338
187
984
625
182
638
194
530
298
546
710
<1225125 bytes omitted>
用户输出
1550182707086
Special Judge 信息
Files user_out and answer differ
系统信息
Exited with return code 0
15201
908
169
997
372
674
852
20
800
436
627
620
732
866
516
456
620
806
422
260
<288163 bytes omitted>
用户输出
15943257138
Special Judge 信息
Files user_out and answer differ
系统信息
Exited with return code 0
28101
858
8
80
704
892
252
373
456
748
158
520
237
7
866
976
16
539
288
960
420
<551205 bytes omitted>
用户输出
34081360138
Special Judge 信息
Files user_out and answer differ
系统信息
Exited with return code 0