Luogu
LOJ
UOJ
BZOJ
可以直接贪心，但是用模拟费用流推的话会更轻松。
首先有一个显然的建图方式：
\(S\)到\(0\)流量为\(k\)，费用为\(0\)。
\(0\)到\(a_i\)流量为\(1\)，费用为\(-a_i\)。
\(a_i\)到\(b_i\)流量为\(1\)，费用为\(0\)。
\(b_i\)到\(T\)流量为\(1\)，费用为\(-b_i\)。
\(a_i\)到\(c\)流量为\(1\)，费用为\(0\)。
\(c\)到\(d\)流量为\(k-l\)，费用为\(0\)。
\(d\)到\(b_i\)流量为\(1\)，费用为\(0\)。
然后我们来模拟一下费用流。
首先我们肯定先把\(c->d\)这里流满，因为这个是没有\(a_i->b_i\)的配对限制的，一定会更优。
我们先在左右各选\(k-l\)（可能有重复的），能够直接匹配流\(a_i->b_i\)，否则走\(c->d\)。
接下来我们先把\(c->d\)流满。
也就是直接在\(a,b\)中各选一个最大的。
然后我们接下来每次保证增加一对\(a_i->b_i\)，这样就能够保证正确性了。
这里有三种情况：
第一种：我们选一个\(a_i,b_i\)都未选的\(a_i+b_i\)最大的。
第二种：对于一个已被选择的\(a_i\)（对应的\(b_i\)尚未被选），我们给它\(b_i\)配对，并且在未被选的\(a_j\)中挑一个最大的。
反应在流量网络上就是这样：
原本是\(a_i->c->d->b_x\)（这个\(b_x\)实际上可以是任意一个流量从\(d\)来的点）。
我们把它改成\(a_i->b_i\)，\(a_j->c->d->b_x\)。
第三种：把第二种的\(a,b\)反过来。
这样我们每次选取能够使答案增加最大的一种方法走，就能够解决这个问题了。
具体而言，我们需要开几个堆记录未被选的\(a_i,b_i,a_i+b_i\)的最大值的下标\(i\)，已选的\(a_i(b_i)\)对应的\(b_i(a_i)\)中最大值的下标\(i\)。
代码比较长，凑合着看吧。
#include<bits/stdc++.h>
#define LL long long
using namespace std;
namespace IO
{
char ibuf[(1<<21)+1],*iS,*iT;
char Get(){return (iS==iT? (iT=(iS=ibuf)+fread(ibuf,1,(1<<21)+1,stdin),(iS==iT? EOF:*iS++)):*iS++);}
int read(){int x=0;char c=Get();while(!isdigit(c))c=Get();while(isdigit(c))x=x*10+(c^48),c=Get();return x;}
}
using namespace IO;
int max(int a,int b){return a>b? a:b;}
const int N=1000007;
LL ans;int T,n,l,k,id[N],a[N],b[N],fa[N],fb[N];
struct nodea{int id;};struct nodeb{int id;};struct nodec{int id;};
int operator<(nodea i,nodea j){return a[i.id]<a[j.id];}
int operator<(nodeb i,nodeb j){return b[i.id]<b[j.id];}
int operator<(nodec i,nodec j){return a[i.id]+b[i.id]<a[j.id]+b[j.id];}
int cmpa(int i,int j){return a[i]>a[j];}
int cmpb(int i,int j){return b[i]>b[j];}
priority_queue<nodea>ra,sa;priority_queue<nodeb>rb,sb;priority_queue<nodec>rc;
int main()
{
int i,j,num,va,vb,vc,mx;
for(T=read();T;--T)
{
n=read(),k=read(),l=read(),memset(fa,0,sizeof fa),memset(fb,0,sizeof fb),ans=num=va=vb=vc=0;
while(!ra.empty())ra.pop();while(!rb.empty())rb.pop();while(!sa.empty())sa.pop();while(!sb.empty())sb.pop();while(!rc.empty())rc.pop();
for(i=1;i<=n;++i) a[i]=read(),id[i]=i;
for(i=1;i<=n;++i) b[i]=read();
sort(id+1,id+n+1,cmpa); for(i=1;i<=k-l;++i) ans+=a[id[i]],fa[id[i]]=1;
sort(id+1,id+n+1,cmpb); for(i=1;i<=k-l;++i) ans+=b[id[i]],fb[id[i]]=1;
for(i=1;i<=n;++i)
if(fa[i]&&fb[i]) ++num;
else if(fa[i]) rb.push((nodeb){i}),sb.push((nodeb){i});
else if(fb[i]) ra.push((nodea){i}),sa.push((nodea){i});
else ra.push((nodea){i}),rb.push((nodeb){i}),rc.push((nodec){i});
while(l--)
{
while(!ra.empty()&&fa[ra.top().id])ra.pop();
while(!rb.empty()&&fb[rb.top().id])rb.pop();
while(!rc.empty()&&(fa[rc.top().id]||fb[rc.top().id]))rc.pop();
while(!sa.empty()&&fa[sa.top().id])sa.pop();
while(!sb.empty()&&fb[sb.top().id])sb.pop();
if(num)
{
i=ra.top().id,j=rb.top().id,ans+=a[i]+b[j],fa[i]=fb[j]=1,--num;
if(!fb[i]) sb.push((nodeb){i});
if(!fa[j]) sa.push((nodea){j});
if(i==j)++num;else{if(fa[i]&&fb[i])++num;if(fa[j]&&fb[j])++num;}
continue;
}
if(!sb.empty()) i=ra.top().id,j=sb.top().id,va=a[i]+b[j];
if(!sa.empty()) i=rb.top().id,j=sa.top().id,vb=a[j]+b[i];
if(!rc.empty()) i=rc.top().id,vc=a[i]+b[i];
mx=max(vc,max(va,vb)),ans+=mx;
if(va==mx) i=ra.top().id,j=sb.top().id,fa[i]=fb[j]=1,fb[i]? ++num:(sb.push((nodeb){i}),0);
else if(vb==mx) i=rb.top().id,j=sa.top().id,fa[j]=fb[i]=1,fa[i]? ++num:(sa.push((nodea){i}),0);
else if(vc==mx) i=rc.top().id,rc.pop(),fa[i]=fb[i]=1;
}
printf("%lld\n",ans);
}
}
当然如果我们一开始啥都不干（把“我们先在左右各选\(k-l\)（可能有重复的），能够直接匹配流\(a_i->b_i\)，否则走\(c->d\)”这一步去掉）也是可行的，改几个地方就行了。
代码会短一些，不过常数会大一些。
#include<bits/stdc++.h>
#define LL long long
using namespace std;
namespace IO
{
char ibuf[(1<<21)+1],*iS,*iT;
char Get(){return (iS==iT? (iT=(iS=ibuf)+fread(ibuf,1,(1<<21)+1,stdin),(iS==iT? EOF:*iS++)):*iS++);}
int read(){int x=0;char c=Get();while(!isdigit(c))c=Get();while(isdigit(c))x=x*10+(c^48),c=Get();return x;}
}
using namespace IO;
int max(int a,int b){return a>b? a:b;}
const int N=1000007;
LL ans;int T,n,l,k,a[N],b[N],fa[N],fb[N];
struct nodea{int id;};struct nodeb{int id;};struct nodec{int id;};
int operator<(nodea i,nodea j){return a[i.id]<a[j.id];}
int operator<(nodeb i,nodeb j){return b[i.id]<b[j.id];}
int operator<(nodec i,nodec j){return a[i.id]+b[i.id]<a[j.id]+b[j.id];}
int cmpa(int i,int j){return a[i]>a[j];}
int cmpb(int i,int j){return b[i]>b[j];}
priority_queue<nodea>ra,sa;priority_queue<nodeb>rb,sb;priority_queue<nodec>rc;
int main()
{
int i,j,num,va,vb,vc,mx;
for(T=read();T;--T)
{
n=read(),k=read(),l=read(),memset(fa,0,sizeof fa),memset(fb,0,sizeof fb),ans=va=vb=vc=0,num=k-l;
while(!ra.empty())ra.pop();while(!rb.empty())rb.pop();while(!sa.empty())sa.pop();while(!sb.empty())sb.pop();while(!rc.empty())rc.pop();
for(i=1;i<=n;++i) a[i]=read();
for(i=1;i<=n;++i) b[i]=read();
for(i=1;i<=n;++i) ra.push((nodea){i}),rb.push((nodeb){i}),rc.push((nodec){i});
while(k--)
{
while(!ra.empty()&&fa[ra.top().id])ra.pop();
while(!rb.empty()&&fb[rb.top().id])rb.pop();
while(!rc.empty()&&(fa[rc.top().id]||fb[rc.top().id]))rc.pop();
while(!sa.empty()&&fa[sa.top().id])sa.pop();
while(!sb.empty()&&fb[sb.top().id])sb.pop();
if(num)
{
i=ra.top().id,j=rb.top().id,ans+=a[i]+b[j],fa[i]=fb[j]=1,--num;
if(!fb[i]) sb.push((nodeb){i});
if(!fa[j]) sa.push((nodea){j});
if(i==j)++num;else{if(fa[i]&&fb[i])++num;if(fa[j]&&fb[j])++num;}
continue;
}
if(!sb.empty()) i=ra.top().id,j=sb.top().id,va=a[i]+b[j];
if(!sa.empty()) i=rb.top().id,j=sa.top().id,vb=a[j]+b[i];
if(!rc.empty()) i=rc.top().id,vc=a[i]+b[i];
mx=max(vc,max(va,vb)),ans+=mx;
if(va==mx) i=ra.top().id,j=sb.top().id,fa[i]=fb[j]=1,fb[i]? ++num:(sb.push((nodeb){i}),0);
else if(vb==mx) i=rb.top().id,j=sa.top().id,fa[j]=fb[i]=1,fa[i]? ++num:(sa.push((nodea){i}),0);
else if(vc==mx) i=rc.top().id,rc.pop(),fa[i]=fb[i]=1;
}
printf("%lld\n",ans);
}
}
Luogu
LOJ
UOJ
BZOJ
线段树套set优化dij。
每次把当前距离最短的点拿出来扩展，然后把扩展到的点从set中删掉。
#include<bits/stdc++.h>
#define pi pair<int,int>
#define ls p<<1
#define rs p<<1|1
#define mid ((l+r)>>1)
#define fi first
#define se second
using namespace std;
namespace IO
{
char ibuf[(1<<21)+1],obuf[(1<<21)+1],st[15],*iS,*iT,*oS=obuf,*oT=obuf+(1<<21);
char Get(){return (iS==iT? (iT=(iS=ibuf)+fread(ibuf,1,(1<<21)+1,stdin),(iS==iT? EOF:*iS++)):*iS++);}
void Flush(){fwrite(obuf,1,oS-obuf,stdout),oS=obuf;}
void Put(char x){*oS++=x;if(oS==oT)Flush();}
int read(){int x=0,c=Get();while(!isdigit(c))c=Get();while(isdigit(c))x=x*10+c-48,c=Get();return x;}
void write(int x){int top=0;if(!x)Put(‘0‘);while(x)st[++top]=(x%10)+48,x/=10;while(top)Put(st[top--]);Put(‘\n‘);}
}
using namespace IO;
const int N=150007;
int n,m,w,h,dis[N],vis[N];
struct node{int x,y,id;}a[N>>1];
int operator<(node a,node b){return a.y<b.y||(a.y==b.y&&a.id<b.id);}
struct edge{int p,t,l1,r1,l2,r2;}e[N];
vector<int>E[N];set<node>s[N<<1];priority_queue<pi,vector<pi>,greater<pi>>q;queue<int>del;
void insert(int p,int l,int r,int x)
{
s[p].insert(a[x]);
if(l==r) return ;
a[x].x<=mid? insert(ls,l,mid,x):insert(rs,mid+1,r,x);
}
void erase(int p,int l,int r,int x)
{
s[p].erase(a[x]);
if(l==r) return ;
a[x].x<=mid? erase(ls,l,mid,x):erase(rs,mid+1,r,x);
}
void update(int p,int l,int r,int id,int v)
{
int L=e[id].l1,R=e[id].r1;
if(r<L||l>R||s[p].empty()) return;
if(L<=l&&r<=R)
{
set<node>::iterator it=lower_bound(s[p].begin(),s[p].end(),(node){w+1,e[id].l2,0});
for(;it!=s[p].end()&&it->y<=e[id].r2;++it)
{
dis[it->id]=v,del.push(it->id);
for(int x:E[it->id]) q.push(pi(v+e[x].t,x));
}
while(!del.empty())erase(1,1,w,del.front()),del.pop();
return;
}
update(ls,l,mid,id,v),update(rs,mid+1,r,id,v);
}
void dij()
{
q.push(pi(0,0));pi x;
while(!q.empty()){x=q.top(),q.pop();if(vis[x.se])continue;vis[x.se]=1;update(1,1,w,x.se,x.fi);}
}
int main()
{
n=read(),m=read(),w=read(),h=read();
for(int i=1;i<=n;++i) a[i]=(node){read(),read(),i},insert(1,1,w,i);
for(int i=1;i<=m;++i) e[i]=(edge){read(),read(),read(),read(),read(),read()},E[e[i].p].push_back(i);
e[0]=(edge){0,0,a[1].x,a[1].x,a[1].y,a[1].y},dij();
for(int i=2;i<=n;++i) write(dis[i]);
return Flush(),0;
}
原文：https://www.cnblogs.com/cjoierShiina-Mashiro/p/13006125.html