题解：CF2038H Galactic Council

首先这个题意非常不可做，但是仔细观察会得到一些有用的性质。

首先我们发现他对于所有的 m 个回合都给出了钦定的执政党 p_i，假如说第 i 个回合执政党一共有多少 val_{i} 票，那么对于第 i+1 回合的执政党 p_{i+1} 我们有：

又因为一开始你只能选 p_1，所以我们可以知道任意回合执政党的票数，对于编号小的党派我们只用保证小于 val_i，编号大的党派我们只需要保证小于等于 val_i 即可。

那我们考虑建立这样的一个流模型：

• 首先我们建立超级源点 s 和超级汇点 t，用以控制流量和处理强制流满问题，以及源点 S 和汇点 T。
• 对于每个回合我们把它们单独建一个点记做 u，然后连一条 S\to u 的流量为 1 费用为 0 的边代表分配一个选票。
• 对于每个回合 u 的每个党派 v 我们单独建一个点记做 (u,v)，以下默认 (m+1,v) 等价于 T。
  • 对于每个当前回合的非执政党我们连一条 (u,v)\to (u+1,v) 的流量为当前的最大上界费用为 0 的边。
  • 对于执政党，我们考虑考虑连一条 (u,v)\to (u+1,v) 的流量为 val_u 且必须流满的边，考虑上下界，直接从 s 连一条流量为 val_u 的边到 (u+1,v)，从 (u,v) 连一条流量为 val_v 的边到 t。
• 对于两边点集之间我们连 u\to (u,v) 的一条流量为 1 费用为 a_{v,u} 的边。

然后跑最大费用最大流即可，对于输出方案我们直接对于每个 u 去看哪条出边的流量用光了即可。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>

#define N 5005
#define INF 0x3f3f3f3f

inline int R() {
    int x=0; bool f=0; char c=getchar();
    while (!isdigit(c)) f|=(c=='-'),c=getchar();
    while (isdigit(c)) x=x*10+c-'0',c=getchar();
    return f?-x:x;
}

template<typename T>
void W(T x,char Extra=0) {
    if (x<0) putchar('-'),x=-x; if (x>9) W(x/10);
    putchar(x%10+'0'); if (Extra) putchar(Extra);
}

using namespace std;
int n,m,a[N][N];

int tot=1,s,t,S,T,mcmf,cur[N],head[N],dis[N],vis[N];
struct Node { int to,nxt,dis,val; }e[N*N];

void add(int u,int v,int dis,int val) { e[++tot]=Node{v,head[u],dis,val},head[u]=tot; }

bool SPFA() {
    memcpy(cur,head,((n+1)*m+4)*sizeof(head[0]));
    memset(dis,0x3f,((n+1)*m+4)*sizeof(dis[0]));
    memset(vis,0,((n+1)*m+4)*sizeof(vis[0]));
    queue<int> q; q.push(s); dis[s]=0;
    while (!q.empty()) {
        int u=q.front(); q.pop(); vis[u]=0;
        for (int i=head[u];i;i=e[i].nxt) {
            int v=e[i].to;
            if (e[i].dis and dis[v]>dis[u]+e[i].val) {
                dis[v]=dis[u]+e[i].val;
                if (!vis[v]) q.push(v),vis[v]=1;
            }
        }
    }
    return dis[t]!=INF;
}

int dfs(int u,int flow) {
    if (u==t) return flow;
    int res=0; vis[u]=1;
    for (int i=cur[u];i and flow;i=e[i].nxt) {
        int v=e[i].to; cur[u]=i;
        if (e[i].dis and !vis[v] and dis[v]==dis[u]+e[i].val) {
            int k=dfs(v,min(e[i].dis,flow));
            e[i].dis-=k,e[i^1].dis+=k,res+=k,flow-=k,mcmf+=k*e[i].val;
        }
    }
    vis[u]=0; return res;
}

int p[N],val[N];

int main() {
    n=R(),m=R();
    for (int i=1;i<=m;i++) p[i]=R(),val[i]=val[i-1]+(p[i]>p[i-1]);
    s=0,t=(n+1)*m+1,S=(n+1)*m+2,T=(n+1)*m+3;
    int Sum=0;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++) Sum+=(a[i][j]=R());
    int sum=0;
    for (int i=1;i<=m;i++) {
        add(S,i+n*m,1,0),add(i+n*m,S,0,0);
        for (int j=1;j<=n;j++) {
            add(i+n*m,(i-1)*n+j,1,-a[j][i]),add((i-1)*n+j,i+n*m,0,a[j][i]);
            if (j<p[i]) add((i-1)*n+j,i==m?T:i*n+j,val[i]-1,0),add(i==m?T:i*n+j,(i-1)*n+j,0,0);
            else if (j==p[i]) {
                add(s,i==m?T:i*n+j,val[i],0),add(i==m?T:i*n+j,s,0,0);
                add((i-1)*n+j,t,val[i],0),add(t,(i-1)*n+j,0,0);
                sum+=val[i];
            } else add((i-1)*n+j,i==m?T:i*n+j,val[i],0),add(i==m?T:i*n+j,(i-1)*n+j,0,0);
        }
    }
    add(s,S,m,0),add(S,s,0,0); add(T,t,m,0),add(t,T,0,0);
    int ans=0;
    while (SPFA()) ans+=dfs(s,INF);
    if (ans<sum+m) return W(-1,'\n'),0;
    for (int u=1;u<=m;u++) {
        int res=0;
        for (int i=head[u+n*m];i;i=e[i].nxt) {
            int v=e[i].to;
            if (v>=(u-1)*n+1 and v<=(u-1)*n+n and !e[i].dis) {
                res=v-(u-1)*n;
                break;
            }
        }
        W(res,' ');
    }
    return 0;
}