CoderForces-1354F Summoning Minions

DP 费用流
题解
发布日期:   2020-05-24
更新日期:   2020-05-24
文章字数:   1.4k
阅读时长:   8 分
阅读次数:  

传送门：CoderForces-1354F

思路分析

要使价值最大，每一个都要用上，先确定k-1个人，然后重复使用第k个位置，直到最后一个人，这样肯定是最优的，我们可以发现，在确定的人里面，他们的$b_i$是单调递增的，所以可以按$b_i$从小到大排序，然后进行DP，$dp[i][j]$表示前$i$个人确定了$j$个人的最大价值

因为数据范围很小，所以这道题还可以通过费用流求解：

  1. 超级源点–>每个人 流量为1，费用为0
  2. 每个人–>每个位置，流量为1，费用分情况讨论
  3. 每个位置–>超级汇点，流量为1，费用为0

因为这里需要的是最大费用最大流，所以将费用变为负的，求出来的就是最大费用了
记录路径的话，就看边的流量剩余情况就行了

DP代码


#include <bits/stdc++.h>
#define ls x<<1
#define rs x<<1|1
#define fi first
#define se second
#define ll long long
#define pb push_back
#define mp make_pair
#define fun function
#define sz(x) (x).size()
#define lowbit(x) (x)&(-x)
#define all(x) (x).begin(),(x).end()
#define mem(a,b) memset(a,b,sizeof(a))

namespace FastIO {
#define BUF_SIZE 100000
#define OUT_SIZE 100000
    bool IOerror=0;
    inline char nc() {
        static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE;
        if(p1==pend) {
            p1=buf;
            pend=buf+fread(buf,1,BUF_SIZE,stdin);
            if(pend==p1) {
                IOerror=1;
                return -1;
            }
        }
        return *p1++;
    }
    inline bool blank(char ch) {
        return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';
    }
    template<class T> inline bool read(T &x) {
        bool sign=0;
        char ch=nc();
        x=0;
        for(; blank(ch); ch=nc());
        if(IOerror)return false;
        if(ch=='-')sign=1,ch=nc();
        for(; ch>='0'&&ch<='9'; ch=nc())x=x*10+ch-'0';
        if(sign)x=-x;
        return true;
    }
    template<class T,class... U>bool read(T& h,U&... t) {
        return read(h)&&read(t...);
    }
#undef OUT_SIZE
#undef BUF_SIZE
};
using namespace std;
using namespace FastIO;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int INF = 0x3f3f3f3f;
const int N = 80;

struct node{
    int a,b,id;
}a[N];

int dp[N][N];


int main() {

#ifdef xiaofan
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif

    int t;
    cin>>t;
    while(t--){
        int n,k;
        read(n,k);
        mem(dp,-INF);
        dp[0][0]=0;
        for(int i=1;i<=n;i++) read(a[i].a,a[i].b),a[i].id=i;
        sort(a+1,a+1+n,[](node x,node y){
            return x.b<y.b;
        });
        for(int i=1;i<=n;i++){
            for(int j=0;j<=k;j++){
                dp[i][j]=max(dp[i][j],dp[i-1][j]+a[i].b*(k-1));
                if(j) dp[i][j]=max(dp[i][j],dp[i-1][j-1]+a[i].a+a[i].b*(j-1));
            }
        }
        vector<int>ins,del;
        printf("%d\n",k+(n-k)*2);
        int now=dp[n][k],cnt=k;
        for(int i=n;i>=1;i--){
            if(dp[i-1][cnt]+a[i].b*(k-1)==dp[i][cnt]){
                del.pb(a[i].id);
                now=dp[i-1][cnt];
            }else{
                ins.pb(a[i].id);
                cnt--;
                now=dp[i-1][cnt];
            }
        }
        reverse(all(ins));
        for(int i=0;i<sz(ins)-1;i++) cout<<ins[i]<<" ";
        for(auto x:del) cout<<x<<" "<<-x<<" ";
        cout<<ins[sz(ins)-1]<<endl;
    }




    return 0;
}
&nbsp;

费用流代码

#include <bits/stdc++.h>
#define ls x<<1
#define rs x<<1|1
#define fi first
#define se second
#define ll long long
#define pb push_back
#define mp make_pair
#define fun function
#define sz(x) (x).size()
#define lowbit(x) (x)&(-x)
#define all(x) (x).begin(),(x).end()
#define mem(a,b) memset(a,b,sizeof(a))

namespace FastIO {
#define BUF_SIZE 100000
#define OUT_SIZE 100000
    bool IOerror=0;
    inline char nc() {
        static char buf[BUF_SIZE],*p1=buf+BUF_SIZE,*pend=buf+BUF_SIZE;
        if(p1==pend) {
            p1=buf;
            pend=buf+fread(buf,1,BUF_SIZE,stdin);
            if(pend==p1) {
                IOerror=1;
                return -1;
            }
        }
        return *p1++;
    }
    inline bool blank(char ch) {
        return ch==' '||ch=='\n'||ch=='\r'||ch=='\t';
    }
    template<class T> inline bool read(T &x) {
        bool sign=0;
        char ch=nc();
        x=0;
        for(; blank(ch); ch=nc());
        if(IOerror)return false;
        if(ch=='-')sign=1,ch=nc();
        for(; ch>='0'&&ch<='9'; ch=nc())x=x*10+ch-'0';
        if(sign)x=-x;
        return true;
    }
    template<class T,class... U>bool read(T& h,U&... t) {
        return read(h)&&read(t...);
    }
#undef OUT_SIZE
#undef BUF_SIZE
};
using namespace std;
using namespace FastIO;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int INF = 0x3f3f3f3f;
const int N = 222;
const int M = N*N;

struct node {
    int v,flow,w,next;
} e[M];

int head[N],cnt;
int n,m,s,t,k,maxflow,mincost,path[N],pre[N];
int dis[N],vis[N];

inline void ade(int u,int v,int f,int w) {
    e[++cnt].v=v;
    e[cnt].flow=f;
    e[cnt].w=w;
    e[cnt].next=head[u];
    head[u]=cnt;

}

inline void add(int u,int v,int f,int w) {
    ade(u,v,f,w);
    ade(v,u,0,-w);
}

inline bool spfa() {
    mem(dis,INF);
    mem(vis,0);
    mem(pre,-1);
    dis[s]=0;
    vis[s]=1;
    queue<int>q;
    q.push(s);
    while(!q.empty()) {
        int u=q.front();
        vis[u]=0;
        q.pop();
        for(int i=head[u]; i; i=e[i].next) {
            int v=e[i].v;
            int w=e[i].w;
            if(e[i].flow>0 && dis[v]>dis[u]+w) {
                dis[v]=dis[u]+w;
                pre[v]=u;
                path[v]=i;
                if(!vis[v]) {
                    q.push(v);
                    vis[v]=1;
                }
            }
        }
    }
    return pre[t]!=-1;
}

inline void EK() {
    while(spfa()) {
        int mi=INF;
        for(int i=t; i!=s; i=pre[i])
            mi=min(mi,e[path[i]].flow);
        for(int i=t; i!=s; i=pre[i]) {
            e[path[i]].flow-=mi;
            e[path[i]^1].flow+=mi;
        }
        maxflow+=mi;
        mincost+=dis[t]*mi;
    }
}

inline init() {
    mem(head,0);
    cnt=1;
    s=N-1;
    t=N-2;
    maxflow=0;
    mincost=0;
}

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

int main() {

#ifdef xiaofan
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif

    int cas;
    read(cas);
    while(cas--) {
        read(n,k);
        init();
        for(int i=1; i<=n; i++) read(a[i],b[i]);
        for(int i=1; i<=n; i++) {
            add(s,i,1,0);
            add(i+n,t,1,0);
        }
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                if(j<=k-1) add(i,j+n,1,-(a[i]+b[i]*(j-1)));
                else if(j==n) add(i,j+n,1,-(a[i]+b[i]*(k-1)));
                else add(i,j+n,1,-(b[i]*(k-1)));
            }
        }
        EK();
        for(int i=1; i<=n; i++) {
            for(int j=head[i]; j; j=e[j].next) {
                int v=e[j].v;
                int flow=e[j].flow;
                if(flow==0 && v>n && v<=2*n) ans[v-n]=i;
            }
        }
        printf("%d\n",k+(n-k)*2);
        for(int i=1; i<=n; i++) {
            printf("%d ",ans[i]);
            if(i>k-1 && i!=n) printf("%d ",-ans[i]);
        }
        puts("");
    }




    return 0;
}
&nbsp;
文章作者: 小凡
文章链接: http://yoursite.com/2020/05/24/CF1354F/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 小凡 !
DP 费用流
赏
评论
  目录
隐藏
{% if theme.sakura.enable %}{% endif %}