【ACM-ICPC 2018 焦作赛区网络预赛 F.Modular Production Line】 区间K覆盖 网络流

F. Modular Production Line
区间K覆盖模型,用费用流解.只是这题$N$可达$1e5$,需要将点离散化.（网络流复杂度$o(v^2 E）$)
建模方式步骤:
1.对权值为$w$的区间$[u,v]$,加边$id(u)->id(v+1)$,容量为1,费用为-w;
这样最后的结果取反就是最大值
2.对所有相邻的点(离散化之后的点)加边$id(i)->id(i+1)$,容量为正无穷,费用为$0$;
3.建立源点汇点,由源点s向最左侧的点加边,容量为K,费用为0,由最右侧的点向汇点加边,容量为K,费用为$0$
4.对于这种涉及到点覆盖的问题，单个点有使用次数，一般需要$u->（v+1）$建边，这样能够避免区间点重合
5.跑出最大流后,最小费用取绝对值就是能获得的最大权
代码

//复杂度o（v^2e)
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
#define ll long long
#define pb push_back
#define mp make_pair
using namespace std;
const int maxn=1e3+5;
const int inf=0x3f3f3f3f;
const int maxm=1e5+5;
struct node
{int u,to,nxt,w,val;
}edge[maxm];
int head[maxn],tot;
int dis[maxn],vis[maxn];
int ss,ee;
void addedge(int u,int v,int w,int val)
{edge[tot].u=u;edge[tot].to=v;edge[tot].nxt=head[u];edge[tot].val=val;edge[tot].w=w;head[u]=tot++;edge[tot].u=v;edge[tot].to=u;edge[tot].nxt=head[v];edge[tot].val=-val;edge[tot].w=0;head[v]=tot++;
}
int pre[maxn],aa[maxn];
bool  spfa(int &flow,int &cost)
{memset(dis,inf,sizeof(dis));memset(vis,0,sizeof(vis));memset(pre,-1,sizeof(pre));dis[ss]=0;vis[ss]=true;aa[ss]=inf;pre[ss]=ss;queue<int>q;q.push(ss);while(!q.empty()){int u=q.front();q.pop();vis[u]=false;for(int i=head[u];i+1;i=edge[i].nxt){int v=edge[i].to;if(edge[i].w>0&&dis[v]>dis[u]+edge[i].val){dis[v]=dis[u]+edge[i].val;pre[v]=i;aa[v]=min(aa[u],edge[i].w);if(!vis[v]){vis[v]=true;q.push(v);}}}}if(dis[ee]==inf)return 0;flow+=aa[ee];cost+=dis[ee]*aa[ee];//cout<<aa[ee]<<' '<<dis[ee]<<endl;int uu=ee;while(uu!=ss){edge[pre[uu]].w-=aa[ee];edge[pre[uu]^1].w+=aa[ee];uu=edge[pre[uu]].u;}return 1;
}
int ek()
{int flow=0,cost=0;while(spfa(flow,cost));return cost;
}
map<int,int>con;
struct node1
{int u,v,w;node1(){};node1(int a,int b,int c){u=a,v=b,w=c;};
}item[maxn];
int main()
{int t;scanf("%d",&t);while(t--){con.clear();memset(head,-1,sizeof(head));tot=0;int n,k,m;scanf("%d%d%d",&n,&k,&m);for(int i=0;i<m;i++){int a,b,w;scanf("%d%d%d",&a,&b,&w);b++;//像这种点有限制，为了避免点的覆盖，可以令尾节点+1，这样可以实现con[a]=con[b]=1;item[i]=node1(a,b,w);}map<int,int>::iterator it;//map自动排序int cnt1=0;for(it=con.begin();it!=con.end();it++){int id=it->first;con[id]=++cnt1;//离散化}ss=cnt1+2;ee=cnt1+3;for(int i=1;i<cnt1;i++){addedge(i,i+1,inf,0);}addedge(ss,1,k,0);addedge(cnt1,ee,k,0);for(int i=0;i<m;++i){int u,v;u = item[i].u, v = item[i].v;u = con[u], v =con[v];addedge(u,v,1,-item[i].w);}int ans=ek();printf("%d\n",-ans);}return 0;
}