计蒜客 ICPC焦作网络赛 Modular Production Line(区间k覆盖 + 最小费用最大流)
程序员文章站
2022-06-04 12:07:30
...
大致题意:给你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);
}
}