美しいミズキ

1
输入格式:
2
第1行包含2个整数：n表示农田数量，m表示水管数量。
3
接下来m行，每行包含3个整数：a, b, c，表示从农田a到农田b有一条有向水管，其流量限制为c。农田的编号从1到n。
4

5
输出格式:
6
输出一个整数，表示从1号农田到n号农田的最大流量。
7

8
输入示例：
9
4 5
10
1 2 10
11
1 3 5
12
2 3 5
13
2 4 20
14
3 4 5
15

16
输出示例：
17
15

1
# 读入
2
n, m = map(int, input().split())
3
edges = []
4
for _ in range(m):
5
    a, b, c = map(int, input().split())
6
    edges.append((a, b, c))
7

8
# 决策变量：每条边上的流量
9
x = cp.Variable(m)
10

11
constraints = []
12

13
# 1. 容量约束
14
for i, (a, b, c) in enumerate(edges):
15
    constraints.append(x[i] >= 0)
16
    constraints.append(x[i] <= c)
17

18
# 2. 中间点流量守恒
19
for k in range(2, n):   # 2 ~ n-1
20
    inflow = 0
21
    outflow = 0
22
    for i, (a, b, c) in enumerate(edges):
23
        if b == k:
24
            inflow += x[i]
25
        if a == k:
26
            outflow += x[i]
27
    constraints.append(inflow == outflow)
28

29
# 3. 目标：最大化源点1的净流出
30
source_out = 0
31
source_in = 0
32
for i, (a, b, c) in enumerate(edges):
33
    if a == 1:
34
        source_out += x[i]
35
    if b == 1:
36
        source_in += x[i]
37

38
objective = cp.Maximize(source_out - source_in)
39

40
# 求解
41
prob = cp.Problem(objective, constraints)
42
prob.solve()
43

44
# 输出结果
45
print(round(prob.value))

1
输入格式：
2
第1行：一个整数 n，表示城市数量。
3
接下来的n行：每行包含n个整数，表示城市之间的距离矩阵。
4

5
输出格式：
6
输出一个整数，表示总行程的最短距离。
7

8
输入示例：
9
5
10
0 1050 1420 1270 460
11
1050 0 1200 240 1100
12
1420 1200 0 1950 1760
13
1270 240 1950 0 1270
14
460 1100 1760 1270 0
15

16
输出示例：
17
4590

1
# ---------- 决策变量 ----------
2
# x[i, j] = 1 表示从 i 到 j
3
x = cp.Variable((n, n), boolean=True)
4

5
# MTZ 顺序变量
6
u = cp.Variable(n)
7

8
constraints = []
9

10
# ---------- 基本约束 ----------
11
# 不允许自己到自己
12
constraints.append(cp.diag(x) == 0)
13

14
# 每个城市恰好出发一次
15
for i in range(n):
16
    constraints.append(cp.sum(x[i, :]) == 1)
17

18
# 每个城市恰好到达一次
19
for j in range(n):
20
    constraints.append(cp.sum(x[:, j]) == 1)
21

22
# ---------- MTZ 子回路消除 ----------
23
# 固定第0个城市作为起点
24
constraints.append(u[0] == 0)
25

26
for i in range(1, n):
27
    constraints.append(u[i] >= 1)
28
    constraints.append(u[i] <= n - 1)
29

30
for i in range(1, n):
31
    for j in range(1, n):
32
        if i != j:
33
            constraints.append(u[i] - u[j] + n * x[i, j] <= n - 1)  # 如果选定了 i->j，此时x[i, j] = 1，则 u[i] < u[j]
34

35
# ---------- 目标函数 ----------
36
objective = cp.Minimize(cp.sum(cp.multiply(D, x)))

1
输入格式:
2

3
第1行包含3个整数：n表示城市数量，m表示道路数量，k表示查询数量。
4

5
接下来m行，每行包含3个整数：a, b, t，表示城市a和城市b之间有一条双向道路，行驶这条道路需要t时间。城市的编号从1到n。
6

7
接下来k行，每行包含2个整数：s, d，表示一次查询，从城市s出发到达城市d。
8

9
输出格式：
10

11
输出k行，每行包含一个整数，表示对应查询的最短时间。
12

13
如果无法到达目标城市，输出-1。
14

15
输入示例：
16
4 5 2
17
1 2 3
18
1 3 1
19
2 4 2
20
3 4 4
21
2 3 5
22
1 4
23
2 4
24

25
输出示例：
26
5
27
2

1
input = sys.stdin.readline
2

3
def solve_one_query(n, edges, s, t):
4
    # 无向边拆成有向边
5
    arcs = []
6
    cost = []
7
    for a, b, w in edges:
8
        arcs.append((a, b))
9
        cost.append(w)
10
        arcs.append((b, a))
11
        cost.append(w)
12

13
    m = len(arcs)
14

15
    # 决策变量：是否选第i条弧 0或者1
16
    x = cp.Variable(m, boolean=True)
17

18
    constraints = []
19

20
    # 流量平衡约束
21
    for i in range(1, n + 1):
22
        outflow = 0
23
        inflow = 0
24
        for e, (u, v) in enumerate(arcs):
25
            if u == i:
26
                outflow += x[e]   # 这条边被选作路径的起点
27
            if v == i:
28
                inflow += x[e]    # 这条边被选为路径的终点
29

30
        if i == s:
31
            constraints.append(outflow - inflow == 1) # 起点有后继没有前驱
32
        elif i == t:
33
            constraints.append(outflow - inflow == -1) # 终点有前驱没有后继
34
        else:
35
            constraints.append(outflow - inflow == 0) # 中间的点必定有前驱和后继
36

37
    # 目标函数
38
    objective = cp.Minimize(sum(cost[e] * x[e] for e in range(m)))
39

40
    # 建立问题
41
    prob = cp.Problem(objective, constraints)
42

43
    # 求解
44
    prob.solve()
45

46
    return int(round(prob.value))
47

48

49
# 主程序
50
n, m, k = map(int, input().split())
51
edges = []
52

53
for _ in range(m):
54
    a, b, w = map(int, input().split())
55
    edges.append((a, b, w))
56

57
queries = [tuple(map(int, input().split())) for _ in range(k)]
58

59
for s, t in queries:
60
    print(solve_one_query(n, edges, s, t))

1
输入格式:
2
第1行包含2个整数：n表示城市数量，m表示现有道路数量。
3
接下来m行，每行包含3个整数：a, b, c，表示城市a和城市b之间有一条现有道路，升级成本为c。城市的编号从1到n。
4

5
输出格式:
6
输出一个整数，表示连接所有城市的最低成本。
7

8
输入示例：
9
6 9
10
1 2 3
11
1 3 1
12
1 4 2
13
2 3 2
14
2 5 3
15
3 4 3
16
3 6 5
17
4 5 6
18
5 6 2
19

20
输出示例：
21
10

1
import cvxpy as cp
2
import itertools
3

4
n, m = map(int, input().split())
5

6
edge = []
7
cost = []
8

9
for _ in range(m):
10
    a, b, c = map(int, input().split())
11
    edge.append((a, b))
12
    cost.append(c)
13

14
x = cp.Variable(m, boolean = True)
15

16
constraints = []
17

18
constraints.append(cp.sum(x) == n - 1)
19

20
nodes = list(range(1, n + 1))
21

22
for r in range(2, n):   # 子集大小 2 到 n-1
23
    for S in itertools.combinations(nodes, r):
24
        S = set(S)
25

26
        idx = []
27
        for e, (u, v) in enumerate(edge):
28
            if u in S and v in S:
29
                idx.append(e)
30

31
        if idx:
32
            constraints.append(cp.sum(x[idx]) <= len(S) - 1)
33

34
for i in range(m):
35
    constraints.append(x[i] <= 1)
36
    constraints.append(x[i] >= 0)
37

38
objective = cp.Minimize(cp.sum(cp.multiply(cost, x)))
39

40
prob = cp.Problem(objective, constraints)
41
prob.solve()
42

43
print(int(prob.value));