Codeforces

Luogu

分析

有几个比较显然的结论（证明不会）：

• 一定存在一组最优解，使得所有卡都被摆上去过。感性理解：因为 $b_i\geq 0$ 所以你就算摆上去再拿下来也不会更差。
• 一定存在一组最优解，满足首先摆上 $k-1$ 张卡，再将 $n-k$ 张卡摆上去后立即拿下来，再将剩下的那张卡摆上去。感性理解：此时 $b_i$ 的贡献是最大的，且 $a_i$ 的贡献没有影响。

那么相当于要给所有卡排一个放上去的顺序。考虑二分图匹配，将卡作为左边的点、顺序作为右边的点，连边如下：

• 对于 $j\in[1,k-1]$，从 $i$ 向 $j$ 连费用为 $a_i+b_i(j-1)$ 的边。
• 对于 $j\in[k,n-1]$，从 $i$ 向 $j$ 连费用为 $b_i(k-1)$ 的边。
• 对于 $j=n$，从 $i$ 向 $j$ 连费用为 $a_i+b_i(k-1)$ 的边。

这样子求最大费用最大流，根据残量网络构造方案即可。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=75+10;
const int V=150+10,E=6000+10;

int n,k,a[N],b[N],ans[N];

struct edge { int v,w,c,nxt; } e[E<<1];
int head[V],ecnt;
void addEdge(int u,int v,int w,int c) {
    e[++ecnt]=(edge){v,w,c,head[u]},head[u]=ecnt;
    e[++ecnt]=(edge){u,0,-c,head[v]},head[v]=ecnt;
}

int S,T;
int dis[V],inq[V],lst[V];
int spfa() {
    memset(dis,0x3f,sizeof(dis)); memset(lst,0,sizeof(lst));
    queue<int> Q; Q.push(S); dis[S]=0;
    while (!Q.empty()) {
        int u=Q.front(); Q.pop(),inq[u]=0;
        for (int i=head[u];i;i=e[i].nxt) {
            int v=e[i].v,w=e[i].w,c=e[i].c;
            if (w&&dis[u]+c<dis[v]) {
                dis[v]=dis[u]+c,lst[v]=i;
                if (!inq[v]) Q.push(v),inq[v]=1;
            }
        }
    }
    return lst[T]!=0;
}
int mcmf() {
    int res=0;
    while (spfa()) {
        int f=2e9;
        for (int i=lst[T];i;i=lst[e[i^1].v]) f=min(f,e[i].w);
        for (int i=lst[T];i;i=lst[e[i^1].v]) e[i].w-=f,e[i^1].w+=f;
        res+=f*dis[T];
    }
    return res;
}

int main() {
    for (int _=read();_;--_) {
        memset(head,0,sizeof(head)),ecnt=1;
        n=read(),k=read();
        for (int i=1;i<=n;++i) a[i]=read(),b[i]=read();
        S=0,T=n<<1|1;
        for (int i=1;i<=n;++i) addEdge(S,i,1,0);
        for (int i=1;i<=n;++i) addEdge(i+n,T,1,0);
        for (int i=1;i<=n;++i) {
            for (int j=1;j<k;++j) addEdge(i,j+n,1,-(a[i]+b[i]*(j-1)));
            for (int j=k;j<n;++j) addEdge(i,j+n,1,-b[i]*(k-1));
            addEdge(i,n<<1,1,-(a[i]+b[i]*(k-1)));
        }
        mcmf();
        for (int i=1;i<=n;++i)
            for (int j=head[i];j;j=e[j].nxt) {
                if (e[j].v==S||e[j].w) continue;
                ans[e[j].v-n]=i; break;
            }
        printf("%d\n",k+2*(n-k));
        for (int i=1;i<=n;++i) {
            printf("%d ",ans[i]);
            if (k<=i&&i<n) printf("%d ",-ans[i]);
        }
        puts("");
    }
    return 0;
}