2020-2021:teams:legal_string:jxm2001:contest:arc_122
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:legal_string:jxm2001:contest:arc_122 [2021/07/02 17:28] jxm2001 [题解] |
2020-2021:teams:legal_string:jxm2001:contest:arc_122 [2021/07/02 17:29] (当前版本) jxm2001 |
||
|---|---|---|---|
| 行 287: | 行 287: | ||
| 相当于跑 $k$ 次最短路，费用流中的 $\text{spfa}$ 利用优先队列优化据说可以做到 $O(kn\log n)$。 | 相当于跑 $k$ 次最短路，费用流中的 $\text{spfa}$ 利用优先队列优化据说可以做到 $O(kn\log n)$。 | ||
| + | <hidden 查看代码> | ||
| + | <code cpp> | ||
| + | const int MAXN=1e5+5,MAXM=10*MAXN,inf=1e9; | ||
| + | struct Edge{ | ||
| + | int to,cap,w,next; | ||
| + | Edge(int to=0,int cap=0,int w=0,int next=0){ | ||
| + | this->to=to; | ||
| + | this->cap=cap; | ||
| + | this->w=w; | ||
| + | this->next=next; | ||
| + | } | ||
| + | }edge[MAXM<<1]; | ||
| + | int head[MAXN<<2],edge_cnt; | ||
| + | void Clear(){mem(head,-1);edge_cnt=0;} | ||
| + | void Insert(int u,int v,int w,int c){ | ||
| + | edge[edge_cnt]=Edge(v,c,w,head[u]); | ||
| + | head[u]=edge_cnt++; | ||
| + | edge[edge_cnt]=Edge(u,0,-w,head[v]); | ||
| + | head[v]=edge_cnt++; | ||
| + | } | ||
| + | namespace EK{ | ||
| + | int a[MAXN<<2],p[MAXN<<2]; | ||
| + | LL dis[MAXN<<2]; | ||
| + | void MCMF(int s,int t,int &flow,LL &cost){ | ||
| + | flow=0,cost=0; | ||
| + | while(true){ | ||
| + | mem(a,0); | ||
| + | _for(i,0,MAXN<<2)dis[i]=1e18; | ||
| + | priority_queue<pair<LL,int> > q; | ||
| + | a[s]=inf,dis[s]=0; | ||
| + | q.push(make_pair(0,s)); | ||
| + | while(!q.empty()){ | ||
| + | int u=q.top().second; | ||
| + | LL w=q.top().first; | ||
| + | q.pop(); | ||
| + | if(w!=-dis[u])continue; | ||
| + | for(int i=head[u];~i;i=edge[i].next){ | ||
| + | int v=edge[i].to; | ||
| + | if(edge[i].cap&&dis[u]+edge[i].w<dis[v]){ | ||
| + | p[v]=i; | ||
| + | dis[v]=dis[u]+edge[i].w; | ||
| + | a[v]=min(a[u],edge[i].cap); | ||
| + | q.push(make_pair(-dis[v],v)); | ||
| + | } | ||
| + | } | ||
| + | } | ||
| + | if(!a[t]) | ||
| + | return; | ||
| + | for(int i=t;i!=s;i=edge[p[i]^1].to){ | ||
| + | edge[p[i]].cap-=a[t]; | ||
| + | edge[p[i]^1].cap+=a[t]; | ||
| + | } | ||
| + | flow+=a[t]; | ||
| + | cost+=a[t]*dis[t]; | ||
| + | } | ||
| + | } | ||
| + | }; | ||
| + | struct Node{ | ||
| + | int x,y; | ||
| + | bool operator < (const Node &b)const{ | ||
| + | return x<b.x||(x==b.x&&y<b.y); | ||
| + | } | ||
| + | }node[MAXN],st[MAXN]; | ||
| + | int xx[MAXN<<1],yy[MAXN<<1]; | ||
| + | int main() | ||
| + | { | ||
| + | int n=read_int(),m=read_int(),k=read_int(); | ||
| + | Clear(); | ||
| + | _for(i,0,n){ | ||
| + | node[i].x=read_int(); | ||
| + | node[i].y=read_int(); | ||
| + | } | ||
| + | sort(node,node+n); | ||
| + | int pos=0; | ||
| + | _for(i,0,n){ | ||
| + | while(pos&&st[pos].y<=node[i].y)pos--; | ||
| + | st[++pos]=node[i]; | ||
| + | } | ||
| + | int cnt=0; | ||
| + | _rep(i,1,pos){ | ||
| + | xx[cnt]=st[i].x; | ||
| + | yy[cnt++]=st[i].y; | ||
| + | } | ||
| + | _for(i,0,m){ | ||
| + | node[i].x=read_int(); | ||
| + | node[i].y=read_int(); | ||
| + | xx[cnt]=node[i].x; | ||
| + | yy[cnt++]=node[i].y; | ||
| + | } | ||
| + | sort(xx,xx+cnt); | ||
| + | int cntx=unique(xx,xx+cnt)-xx; | ||
| + | sort(yy,yy+cnt); | ||
| + | int cnty=unique(yy,yy+cnt)-yy; | ||
| + | _for(i,1,cntx){ | ||
| + | Insert(i-1,i,xx[i]-xx[i-1],inf); | ||
| + | Insert(i,i-1,0,inf); | ||
| + | } | ||
| + | _for(i,1,cnty){ | ||
| + | Insert(i-1+cntx,i+cntx,0,inf); | ||
| + | Insert(i+cntx,i-1+cntx,yy[i]-yy[i-1],inf); | ||
| + | } | ||
| + | _rep(i,1,pos){ | ||
| + | int u=lower_bound(xx,xx+cntx,st[i-1].x)-xx; | ||
| + | int v=lower_bound(yy,yy+cnty,st[i].y)-yy+cntx; | ||
| + | Insert(u,v,0,inf); | ||
| + | } | ||
| + | _for(i,0,m){ | ||
| + | int u=lower_bound(yy,yy+cnty,node[i].y)-yy+cntx; | ||
| + | int v=lower_bound(xx,xx+cntx,node[i].x)-xx; | ||
| + | Insert(u,v,0,1); | ||
| + | } | ||
| + | int s=cntx+cnty,t=s+1; | ||
| + | Insert(s,lower_bound(yy,yy+cnty,st[1].y)-yy+cntx,0,k); | ||
| + | Insert(lower_bound(xx,xx+cntx,st[pos].x)-xx,t,0,k); | ||
| + | int flow; | ||
| + | LL cost; | ||
| + | EK::MCMF(s,t,flow,cost); | ||
| + | enter(cost); | ||
| + | return 0; | ||
| + | } | ||
| + | </code> | ||
| + | </hidden> | ||
2020-2021/teams/legal_string/jxm2001/contest/arc_122.1625218090.txt.gz · 最后更改: 2021/07/02 17:28 由 jxm2001
