M_sea

CF1107F Vasya and Endless Credits
CodeForcesLuogu分析这题有DP的做法?然而我不会。一天只能选一种方案,考虑二分图最大权匹配。考虑天数...
扫描右侧二维码阅读全文
04
2019/02

CF1107F Vasya and Endless Credits

CodeForces

Luogu

分析

这题有DP的做法?然而我不会。


一天只能选一种方案,考虑二分图最大权匹配。

考虑天数向方案匹配。显然,第$n-i+1$天选第$j$种方案的收益为$a[j]-b[j]*\min(i-1,k[j])$。

然后跑最大费用最大流或者$\texttt{KM}$就行了。

注意到如果收益为负,还不如不选。于是只要在收益为负时强制把收益置成$0$就行了。

然后,因为我常数大,费用流$\texttt{TLE on #5}$,$\texttt{KM TLE on #29}$。

于是我偷税地抄了官方题解,然而并不需要强制收益为$0$。

但是普通的$\texttt{KM}$好像还是需要的。

代码

常数极大的费用流

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#define re register
typedef long long ll;
using namespace std;

inline 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=500+10;
const int INF=0x3f3f3f3f;

int n,s,t;
int a[N],b[N],k[N];
struct Edge { int v,w,nxt; ll c;};
Edge e[1000010];
int head[100010],cnt=0;

inline void addEdge(int u,int v,int w,ll c) {
    e[cnt].v=v,e[cnt].w=w,e[cnt].c=c,e[cnt].nxt=head[u],head[u]=cnt++;
    e[cnt].v=u,e[cnt].w=0,e[cnt].c=-c,e[cnt].nxt=head[v],head[v]=cnt++;
}

ll dis[100010];
int inq[100010],last[100010];

inline int SPFA() {
    memset(dis,0xc0,sizeof(dis));
    memset(inq,0,sizeof(inq));
    memset(last,-1,sizeof(last));
    queue<int> Q; Q.push(s); dis[s]=0,inq[s]=1;
    while (!Q.empty()) {
        int u=Q.front(); Q.pop(); inq[u]=0;
        for (re int i=head[u];i!=-1;i=e[i].nxt) {
            int v=e[i].v; ll c=e[i].c;
            if (e[i].w&&dis[u]+c>dis[v]) {
                dis[v]=dis[u]+c,last[v]=i;
                if (!inq[v]) inq[v]=1,Q.push(v);
            }
        }
    }
    return last[t]!=-1;
}

int main() {
    memset(head,-1,sizeof(head));
    n=read(),s=0,t=n+n+1;
    for (re int i=1;i<=n;++i) a[i]=read(),b[i]=read(),k[i]=read();
    for (re int i=1;i<=n;++i)
        for (re int j=1;j<=n;++j)
            addEdge(i,j+n,1,a[j]-1ll*b[j]*min(i-1,k[j]));
    for (re int i=1;i<=n;++i) addEdge(s,i,1,0);
    for (re int i=1;i<=n;++i) addEdge(i+n,t,1,0);
    ll ans=0;
    while (SPFA()) {
        int flow=INF;
        for (re int i=last[t];i!=-1;i=last[e[i^1].v])
            flow=min(flow,e[i].w);
        for (re int i=last[t];i!=-1;i=last[e[i^1].v])
            e[i].w-=flow,e[i^1].w+=flow;
        if (dis[t]>0) ans+=1ll*dis[t]*flow;
    }
    printf("%lld\n",ans);
    return 0;
}

依然跑不过的KM

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#define re register
typedef long long ll;
using namespace std;

inline 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=500+10;;

int n;
int a[N],b[N],k[N];
ll w[N][N];

ll lx[N],ly[N];
int match[N],s[N],t[N];

inline int Hungary(int i) {
    s[i]=1;
    for (re int j=1;j<=n;++j)
        if (lx[i]+ly[j]==w[i][j]&&!t[j]) {
            t[j]=1;
            if (!match[j]||Hungary(match[j])) return match[j]=i;
        }
    return 0;
}

inline void update() {
    ll p=2e18;
    for (re int i=1;i<=n;++i) {
        if (!s[i]) continue;
        for (re int j=1;j<=n;++j)
            if (!t[j]) p=min(p,lx[i]+ly[j]-w[i][j]);
        }
    for (re int i=1;i<=n;++i) {
        if (s[i]) lx[i]-=p;
        if (t[i]) ly[i]+=p;
    }
}

inline ll KM() {
    for (re int i=1;i<=n;++i) {
        match[i]=lx[i]=ly[i]=0;
        for (re int j=1;j<=n;++j)
            lx[i]=max(lx[i],w[i][j]);
    }
    for (re int i=1;i<=n;++i) {
        while (233) {
            for (re int j=1;j<=n;++j) s[j]=t[j]=0;
            if (Hungary(i)) break;
            else update();
       }
    }
    ll ans=0;
    for (re int i=1;i<=n;++i) ans+=w[match[i]][i];
    return ans;
}

int main() {
    n=read();
    for (re int i=1;i<=n;++i) a[i]=read(),b[i]=read(),k[i]=read();
    for (re int i=1;i<=n;++i)
        for (re int j=1;j<=n;++j)
            w[i][j]=max(a[j]-1ll*b[j]*min(i-1,k[j]),0ll);
    printf("%I64d\n",KM());
    return 0;
}

神奇的官方题解

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#define re register
typedef long long ll;
using namespace std;

inline 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=500+10;
const int INF=0x3f3f3f3f;

int n;
int a[N],b[N],k[N];
ll w[N][N];
ll minv[N],lu[N],lv[N];
int vis[N],p[N],way[N];

inline ll KM() {
    ll ans=0;
    for (re int i=1;i<=n;++i) {
        p[0]=i; int j0=0;
        memset(minv,0x3f,sizeof(minv));
        memset(vis,0,sizeof(vis));
        do {
            vis[j0]=1; int i0=p[j0],j1;
            ll dlt=2e18;
            for (re int j=1;j<=n;++j)
                if (!vis[j]) {
                    ll now=w[i0][j]-lu[i0]-lv[j];
                    if (now<minv[j]) minv[j]=now,way[j]=j0;
                    if (minv[j]<dlt) dlt=minv[j],j1=j;
                }
            for (re int j=0;j<=n;++j) {
                if (vis[j]) lu[p[j]]+=dlt,lv[j]-=dlt;
                else minv[j]-=dlt;
            }
            j0=j1;
        } while (p[j0]);
        do { int j1=way[j0]; p[j0]=p[j1]; j0=j1; } while (j0);
        ans=max(ans,lv[0]);
    }
    return ans; 
}

int main() {
    n=read();
    for (re int i=1;i<=n;++i) a[i]=read(),b[i]=read(),k[i]=read();
    for (re int i=1;i<=n;++i)
        for (re int j=1;j<=n;++j)
            w[i][j]=-a[j]+1ll*b[j]*min(i-1,k[j]);
    printf("%I64d\n",KM());
    return 0;
}
最后修改:2019 年 02 月 19 日 09 : 51 AM

5 条评论

  1. smy

    为什么您都不写题意啊qwq

    1. M_sea
      @smy

      我都看得懂您怎么会看不懂啊qwq

      1. Siyuan
        @M_sea

        窝也看不懂啊 QAQ

        1. M_sea
          @Siyuan

          泥萌都欺负我嘤嘤嘤

      2. smy
        @M_sea

        我看不懂啊

        您好fake啊

发表评论