欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

计蒜客 ICPC焦作网络赛 Modular Production Line(区间k覆盖 + 最小费用最大流)

程序员文章站 2022-06-04 12:07:30
...

计蒜客 ICPC焦作网络赛 Modular Production Line(区间k覆盖 + 最小费用最大流)

计蒜客 ICPC焦作网络赛 Modular Production Line(区间k覆盖 + 最小费用最大流)

计蒜客 ICPC焦作网络赛 Modular Production Line(区间k覆盖 + 最小费用最大流)

 

 

 

大致题意:给你N个机器,可以生产M个物品,每个物品i生产出来需要区间[li,ri]内的机器一起工作。可以产生wi的利润。每个物品只能生产一次,每个机器最多只能工作k次,现在问你能够产生的最大利润。

每个机器只能工作k次,每个物品只能够生产一次,求最大利润。这种问题一看显然就像是一个费用流相关的东西。经过观察分析,你可以发现,这个就是一个区间k覆盖的问题。即一个区间对应一个数值,要求每个点覆盖不超过k次,求最大/最小总和的问题。

具体做法就是构造一个链式图。源点连接1号点,最后一个点连接汇点,两条边流量均为k,费用为0。然后任一点i连接i+1,流量为k,费用为0。对于每一个物品,它所需要的机器区间是[li,ri],于是连边li到ri,流量为1费用为对应的wi的相反数-wi。最后在这个图上跑一个最小费用最大流,最后的最小费用的相反数就是我们的最大利润。

那么这个做法为什么是正确的呢?首先,任意两点间的边流量为k,限制了个点最多只能是有k个流通过。然后对于每一个物品,它建立了边li到ri,可以看到这条边对li之前的点和ri之后的点没有影响。而对于二者之中的点,由于li多了一条直接走到ri的边,但是li的入边没有改变,总流量最多还是k,所以如果我选择了物品i,那么意味着li到ri之间的点的最大流量限制少了一个,恰好对应本题的意思。这样总的构图符合模型也符合本题。

另外,本题物品要求的区间范围比较大,需要进行离散化,而且这个区间也是闭区间,所以得把原区间变成[li,ri+1],这样按照刚刚所说建图即可。具体间代码:

#include<bits/stdc++.h>
#define mod 256
#define LL long long
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define INF 0x3f3f3f3f
#define sf(x) scanf("%d",&x)
#define sc(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define clr(x,n) memset(x,0,sizeof(x[0])*(n+5))
#define file(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
using namespace std;

const int M = 100010;
const int N = 1010;

struct Edge{int from,to,cap,flow,cost;};

namespace MCMF
{
    int n,m,s,t,d[N],p[N],a[N];
    vector<Edge>edges;
    vector<int>g[N];
    bool inq[N];

    void init(int a,int b,int c)
    {
        n=a; s=b; t=c;
        edges.clear();
        for(int i = 0;i<=n;i++)g[i].clear();
    }

    void AddEdge(int from,int to,int cap,int cost)
    {
        edges.push_back(Edge{from,to,cap,0,cost});
        edges.push_back(Edge{to,from,0,0,-cost});
        m=edges.size(); g[from].push_back(m-2); g[to].push_back(m-1);
    }

    bool BellmanFord(int &flow,int &cost)
    {
        for(int i = 0;i<=t;i++)d[i]=INF;
        memset(inq,0,sizeof(inq));
        d[s]=0,a[s]=INF,inq[s]=1,p[s]=0;
        queue<int> q; q.push(s);
        while(!q.empty())
        {
            int u = q.front(); q.pop(); inq[u]=0;
            for(int i = 0;i<g[u].size();i++)
            {
                Edge &e = edges[g[u][i]];
                if(e.cap>e.flow&&d[e.to]>d[u]+e.cost)
                {
                    d[e.to]=d[u]+e.cost; p[e.to]=g[u][i];
                    a[e.to]=min(a[u],e.cap-e.flow);
                    if(!inq[e.to]) {q.push(e.to); inq[e.to]=1;}
                }
            }
        }
        if(d[t]==INF)return false;
        flow+=a[t]; cost+=a[t]*d[t];
        int u = t;
        while(u!=s)
        {
            edges[p[u]].flow+=a[t];
            edges[p[u]^1].flow-=a[t];
            u=edges[p[u]].from;
        }
        return true;
    }

    int Min_cost(int &flow,int &cost)
    {
        flow=0,cost=0;
        while(BellmanFord(flow,cost));
        return cost;
    }
}

int a[N],l[N],r[N],w[N],n,m,s,t;
int num[N];

int main()
{
    int T; sf(T);
    while(T--)
    {
        int x,k;
        sc(x,k,n);
        int tot=0;
        for(int i=1;i<=n;i++)
        {
            sc(l[i],r[i],w[i]);
            num[++tot]=l[i];
            num[++tot]=r[i]+1;
        }
        sort(num+1,num+1+tot);
        tot=unique(num+1,num+1+tot)-num-1;
        s=tot+1; t=s+1;
        MCMF::init(t,s,t);
        for(int i=1;i<tot;i++)
            MCMF::AddEdge(i,i+1,k,0);
        for(int i=1;i<=n;i++)
        {
            int x=lb(num+1,num+1+tot,l[i])-num;
            int y=lb(num+1,num+1+tot,r[i]+1)-num;
            MCMF::AddEdge(x,y,1,-w[i]);
        }
        MCMF::AddEdge(s,1,k,0);
        MCMF::AddEdge(tot,t,k,0);
        int flow,cost;
        MCMF::Min_cost(flow,cost);
        printf("%d\n",-cost);
    }
}