2021-2022 ICPC, NERC, Southern and Volga Russian Regional Contest I. Tetris

I. Tetris

题意：
设定俄罗斯方块的界面大小是 $1e9?k$的， $k<=10$，有 $n<=5000$ 个 高度为1的长方条，每个能覆盖 $l[i],r[i]$ 的区间，每个长方条 有个价值 $w[i]$，问不超出界面，最多能得到多少价值。

思路：
考虑网络流，将每个 $l$ 和 $r$ 离线下来 当作点，每个点按照顺序，向下一个点，连接一条 容量为 $k$，费用为 0 的边。然后选择一个方块放下，即选择一条边 跨过 $l到r$，即从 $l$ 向 $r+1$ 连接一条容量为1，费用为 $?w[i]$ 的边，求最小费用即可。

不怕死用迪杰斯特拉 疯狂 $T101$，可能就是负权使得 同一个点，进入队列的次数太大了，用 $SPFA$就过了，$TAT$

代码：

#include<bits/stdc++.h>
#include<unordered_map>
using namespace std;
#define ll long longinline int qread(){
    int s=0,w=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')w=-1;for (;ch>='0'&&ch<='9';ch=getchar())s=(s<<1)+(s<<3)+(ch^48);return (w==-1?-s:s);}int n,m;typedef pair<ll,int> P;
const int maxn=1e4+50;
const int INF=1e14+7;
bool vis[maxn];
ll cst[maxn],flow[maxn];
int pre[maxn],last[maxn];struct Edge{
    int to,next;ll flow,cst;
}edge[maxn*3];
int head[maxn],num_edge=0;
queue<int>q;
void adeg(int from,int to,ll flow,ll cst)
{
    edge[++num_edge].next=head[from];edge[num_edge].to=to;edge[num_edge].flow=flow;edge[num_edge].cst=cst;head[from]=num_edge;
}
void add(int from,int to,ll flow,ll cst){
    adeg(from,to,flow,cst);adeg(to,from,0,-cst);
}
bool spfa(int s,int t)
{
    memset(cst,0x7f,sizeof(cst));memset(flow,0x7f,sizeof(flow));memset(vis,0,sizeof(vis));q.push(s);vis[s]=1;cst[s]=0;pre[t]=-1;while(!q.empty()){
    int now=q.front();q.pop();vis[now]=0;for (int i=head[now]; i!=-1; i=edge[i].next){
    if (edge[i].flow>0 && cst[edge[i].to]>cst[now]+edge[i].cst){
    cst[edge[i].to]=cst[now]+edge[i].cst;pre[edge[i].to]=now;last[edge[i].to]=i;flow[edge[i].to]=min(flow[now],edge[i].flow);if (!vis[edge[i].to]){
    vis[edge[i].to]=1;q.push(edge[i].to);}}}}return pre[t]!=-1;
}void MCMF(int S,int T,ll &MF,ll &MC)
{
    while (spfa(S,T)){
    int now=T;MF+=flow[T];MC+=flow[T]*cst[T];while (now!=S){
    edge[last[now]].flow-=flow[T];edge[last[now]^1].flow+=flow[T];now=pre[now];}}
}void init(){
    memset(head,-1,sizeof(head));num_edge=-1;//初始化
}
struct node{
    int a,b,w;
}z[5005];
int tot=0;
int ss[10005];
unordered_map<int,int>mpp;
int main(){
    init();n=qread(),m=qread();mpp.clear();for(int i=1;i<=n;i++){
    int a=qread(),b=qread(),c=qread();b++;z[i].w=c;z[i].a=a;z[i].b=b;ss[2*i-1]=a;ss[2*i]=b;}sort(ss+1,ss+1+2*n);for(int i=1;i<=2*n;i++){
    if(!mpp.count(ss[i]))mpp[ss[i]]=++tot;}int s=tot+1;int t=s+1;add(s,1,m,0);for(int i=2;i<=tot;i++){
    add(i-1,i,m,0);}add(tot,t,m,0);for(int i=1;i<=n;i++){
    int l=mpp[z[i].a];int r=mpp[z[i].b];add(l,r,1,-z[i].w);}ll F=0,C=0;MCMF(s,t,F,C); printf("%lld\n",-C);return 0;
}