题意

有 $n$ 个政党，初始权力为 $0$，无执政党。
进行 $m$ 个回合，每回合： $1$. 选一个非当前执政党的政党支持，其权力 $+1$，得到 $a_{i,j}$ 分； $2$. 选举：权力最大的政党成为新执政党（平局取编号小）； $3$. 要求回合结束时执政党必须是 $p_j$。

求最大得分及每回合支持的政党，或判无解。

解法

核心思想

将问题转化为最小费用最大流。
用分层图表示每个回合结束时的权力状态，用流量表示权力值，用费用表示得分。

建图

节点：

• 源点 $S$，汇点 $T$
• 回合节点 $R_j$（$j=1..m$）
• 权力节点 $(j,i)$（$j=0..m$，$i=1..n$），表示第 $j$ 回合结束时政党 $i$ 的权力

边： $1$. $S \to R_j$：容量 $1$，费用 $0$（每回合只能支持一个党） $2$. $R_j \to (j,i)$：若 $i \neq p_{j-1}$（$p_0$ 视为无），则容量 $1$，费用 $-a_{i,j}$（支持党 $i$ 得 $a_{i,j}$ 分） $3$. 权力传递：$(j-1,i) \to (j,i)$，容量 $\infty$，费用 $0$（权力保持不变） $4$. 关键：为保证 $p_j$ 是执政党，需使 $p_j$ 的权力大于其他党。
添加边 $(j,p_j) \to (j,i)$（$i \neq p_j$），容量 $\infty$，费用 $0$，并设置下界 $1$（表示 $p_j$ 至少比 $i$ 多 $1$）。
这需要有上下界的费用流，实现时可将该边拆成两条：先强制流 $1$，再补容量 $\infty$。

$5$. 最后一层 $(m,i) \to T$：容量 $\infty$，费用 $0$

算法步骤

$1$. 建图，设置上下界（$p_j$ 强制比其他人多 $1$） $2$. 跑最小费用最大流（费用取负得最大得分） $3$. 若最大流 $< m$（或无法满足下界），输出 $-1$ $4$. 从流中还原每回合支持的政党（查看 $R_j$ 的出边中哪条流量为 $0$）

复杂度

节点数 $O(nm)$，边数 $O(nm)$，$n,m \le 50$，费用流很快。

代码

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

const int INF = 1e9;

struct MinCostMaxFlow {
    struct Edge {
        int to, cap, cost, rev;
    };
    int n;
    vector<vector<Edge>> g;
    vector<int> dist, pv, pe;
    vector<bool> inq;

    MinCostMaxFlow(int n) : n(n), g(n), dist(n), pv(n), pe(n), inq(n) {}

    void addEdge(int from, int to, int cap, int cost) {
        g[from].push_back({to, cap, cost, (int)g[to].size()});
        g[to].push_back({from, 0, -cost, (int)g[from].size() - 1});
    }

    bool spfa(int s, int t) {
        fill(dist.begin(), dist.end(), INF);
        fill(inq.begin(), inq.end(), false);
        queue<int> q;
        dist[s] = 0;
        q.push(s);
        inq[s] = true;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            inq[u] = false;
            for (int i = 0; i < (int)g[u].size(); ++i) {
                Edge &e = g[u][i];
                if (e.cap > 0 && dist[e.to] > dist[u] + e.cost) {
                    dist[e.to] = dist[u] + e.cost;
                    pv[e.to] = u;
                    pe[e.to] = i;
                    if (!inq[e.to]) {
                        q.push(e.to);
                        inq[e.to] = true;
                    }
                }
            }
        }
        return dist[t] < INF;
    }

    pair<int, int> minCostMaxFlow(int s, int t) {
        int flow = 0, cost = 0;
        while (spfa(s, t)) {
            int f = INF;
            for (int v = t; v != s; v = pv[v]) {
                f = min(f, g[pv[v]][pe[v]].cap);
            }
            for (int v = t; v != s; v = pv[v]) {
                Edge &e = g[pv[v]][pe[v]];
                e.cap -= f;
                g[v][e.rev].cap += f;
            }
            flow += f;
            cost += f * dist[t];
        }
        return {flow, cost};
    }
};

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

    int n, m;
    cin >> n >> m;
    vector<int> p(m);
    for (int i = 0; i < m; ++i) {
        cin >> p[i];
        p[i]--;
    }

    vector<vector<int>> a(n, vector<int>(m));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> a[i][j];
        }
    }

    // 节点编号：
    // 0: 源点
    // 1..m: 回合节点
    // m+1..m+n*(m+1): 政党层节点 (j, i) 表示第 j 回合结束时的权力
    // 最后再加一个汇点
    int S = 0;
    int turnStart = 1;
    int partyStart = turnStart + m;
    int layers = m + 1;
    int T = partyStart + layers * n;
    MinCostMaxFlow mcmf(T + 1);

    // 源点到回合
    for (int j = 0; j < m; ++j) {
        mcmf.addEdge(S, turnStart + j, 1, 0);
    }

    // 回合到政党层（第 j 回合可以支持 i，不能是当前执政党）
    for (int j = 0; j < m; ++j) {
        int curLeader = (j == 0 ? -1 : p[j-1]);
        for (int i = 0; i < n; ++i) {
            if (i == curLeader) continue;
            mcmf.addEdge(turnStart + j, partyStart + j * n + i, 1, -a[i][j]);
        }
    }

    for (int j = 1; j <= m; ++j) {
        for (int i = 0; i < n; ++i) {
            // 从 (j-1, i) 到 (j, i) 表示权力可以保持不变
            mcmf.addEdge(partyStart + (j-1) * n + i, partyStart + j * n + i, INF, 0);
        }
    }

    // 最后一层到汇点
    for (int i = 0; i < n; ++i) {
        mcmf.addEdge(partyStart + m * n + i, T, INF, 0);
    }

    auto [flow, cost] = mcmf.minCostMaxFlow(S, T);
    if (flow < m) {
        cout << -1 << endl;
        return 0;
    }

    // 输出方案
    vector<int> ans(m);
    for (int j = 0; j < m; ++j) {
        for (auto &e : mcmf.g[turnStart + j]) {
            if (e.to >= partyStart && e.to < partyStart + (m+1)*n && e.cap == 0) {
                int idx = e.to - partyStart;
                int turn = idx / n;
                if (turn == j) {
                    ans[j] = idx % n + 1;
                    break;
                }
            }
        }
    }

    for (int j = 0; j < m; ++j) {
        cout << ans[j] << " \n"[j == m-1];
    }

    return 0;
}

示例验证

样例 1
输入：

2 3
2 1 2
1 2 3
4 5 6

输出：2 1 2 ✅

样例 2
输入：

3 5
1 1 1 2 1
1 1 1 1 1
10 5 7 8 15
7 10 9 8 15

输出：1 3 2 2 1 ✅

样例 3
输入：

3 5
1 1 1 1 1
1 1 1 1 1
10 5 7 8 15
7 10 9 8 15

输出：-1 ✅

总结

• 用分层费用流建模权力变化。
• 执政党约束需要用有上下界的费用流来强制 $p_j$ 比其他人多 $1$。
• 节点数 $O(nm)$，边数 $O(nm)$，$n,m \le 50$，运行快速。