【Codeforces 704D】Captain America

Author Avatar
mrsrz 12月 07, 2019

上下界费用流

题目大意：

给定二维平面上的 $n$ 个整点，要给每个整点涂上红、蓝两种颜色中的一种，每个点涂成红色、蓝色分别要花费 $r,b$ 元。

现在有 $m$ 个限制，每个限制会规定某行或某列中，红色点和蓝色点的个数的差不能超过 $d_i$。

问满足所有限制条件的最少花费并输出方案。或输出无解。

题解：

把行和列看成点，点看成边，则我们得到一张二分图。

我们假设所有点都涂成了红色。我们要使一个点从红色变成蓝色，其花费会增加 $b-r$。

考虑限制条件。对于某一行，假设它有 $n$ 个点，其限制为 $d$，其中蓝点的个数为 $k$，那么有：

也就是说，对每个有限制的行/列，其蓝点的个数都在一个限制范围内。

观察我们得到的二分图。我们需要选一些边，表示把这些边从红色改成蓝色。并使二分图上的每个点的度都在给定的限制内，还要使花费最小。

对二分图跑上下界最小费用可行流即可，由于是二分图，复杂度是正确的。输出方案只需要看哪些边被流过即可。

注意，如果 $b<r$，那么建完图后会存在负环。只需要把红色和蓝色交换一下即可。

无解的情况特判掉。

Code：

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<cstdlib>
using namespace std;
typedef long long LL;
const int N=5e5+6,inf=0x3f3f3f3f;
inline void failed(){cout<<"-1\n";exit(0);}
int n,m,Red,Blue,nod,head[N],cnt=1,dlt[N],X[N],Y[N],iter[N];
int Lx[N],Ly[N],Rx[N],Ry[N],Dx[N],Dy[N];
int degX[N],degY[N];
int S,T,TT;
int Id[N];
LL dis[N];
bool vis[N];
vector<int>vX,vY;
LL ans;
struct edge{
    int to,nxt,cap,cost;
}e[N<<2];
inline int addedge(int u,int v,int cap,int cost){
    e[++cnt]=(edge){v,head[u],cap,cost},head[u]=cnt;
    e[++cnt]=(edge){u,head[v],0,-cost},head[v]=cnt;
    return cnt-1;
}
inline void AddEdgE(int u,int v,int L,int R,int cost){
    ans+=(LL)cost*L,dlt[u]-=L,dlt[v]+=L;addedge(u,v,R-L,cost);
}
int q[1048576];
int dfs(int u,int f){
    if(u==TT||!f)return f;
    vis[u]=1;
    int ret=0;
    for(int&i=iter[u];i;i=e[i].nxt)
        if(e[i].cap&&!vis[e[i].to]&&dis[e[i].to]==dis[u]+e[i].cost){
            int d=dfs(e[i].to,min(f,e[i].cap));
            e[i].cap-=d,e[i^1].cap+=d,f-=d,ret+=d;
            if(!f)break;
        }
    vis[u]=0;
    return ret;
}
bool MCMF(){
    memset(dis,0x3f,sizeof dis);
    dis[0]=0;
    int h=0,t=1;
    q[0]=0;
    while(h!=t){
        int u=q[h++];
        h&=1048575;
        vis[u]=0;
        for(int i=head[u];i;i=e[i].nxt)
            if(e[i].cap&&dis[e[i].to]>dis[u]+e[i].cost){
                dis[e[i].to]=dis[u]+e[i].cost;
                if(!vis[e[i].to]){
                    vis[e[i].to]=1;
                    q[t++]=e[i].to;
                    t&=1048575;
                }
            }
    }
    if(dis[TT]>1e18)return 0;
    memcpy(iter,head,sizeof head);
    ans+=dfs(0,inf)*dis[TT];
    return 1;
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m>>Red>>Blue;
    bool tag=0;
    if(Red>Blue)swap(Red,Blue),tag=1;
    for(int i=1;i<=n;++i){
        cin>>X[i]>>Y[i];
        vX.push_back(X[i]);
        vY.push_back(Y[i]);
    }
    sort(vX.begin(),vX.end());
    sort(vY.begin(),vY.end());
    vX.erase(unique(vX.begin(),vX.end()),vX.end());
    vY.erase(unique(vY.begin(),vY.end()),vY.end());
    for(int i=0;i<vX.size();++i)Lx[i]=++nod,Rx[i]=++nod;
    for(int i=0;i<vY.size();++i)Ly[i]=++nod,Ry[i]=++nod;
    S=++nod,T=++nod,TT=++nod;
    memset(Dx,0x3f,sizeof Dx);
    memset(Dy,0x3f,sizeof Dy);
    while(m--){
        int t,x,d;
        cin>>t>>x>>d;
        if(t==1){
            int id=lower_bound(vX.begin(),vX.end(),x)-vX.begin();
            if(id<vX.size()&&vX[id]==x)Dx[id]=min(Dx[id],d);
        }else{
            int id=lower_bound(vY.begin(),vY.end(),x)-vY.begin();
            if(id<vY.size()&&vY[id]==x)Dy[id]=min(Dy[id],d);
        }
    }
    ans=(LL)Red*n;
    for(int i=1;i<=n;++i){
        int x=lower_bound(vX.begin(),vX.end(),X[i])-vX.begin();
        int y=lower_bound(vY.begin(),vY.end(),Y[i])-vY.begin();
        Id[i]=addedge(Rx[x],Ly[y],1,Blue-Red);
        ++degX[x],++degY[y];
    }
    for(int i=0;i<vX.size();++i){
        addedge(S,Lx[i],n,0);
        if(Dx[i]>1e9){
            addedge(Lx[i],Rx[i],n,0);
            continue;
        }
        int L=(degX[i]-Dx[i]+1)/2,R=(degX[i]+Dx[i])/2;
        if(L>R)failed();
        AddEdgE(Lx[i],Rx[i],L,R,0);
    }
    for(int i=0;i<vY.size();++i){
        addedge(Ry[i],T,n,0);
        if(Dy[i]>1e9){
            addedge(Ly[i],Ry[i],n,0);
            continue;
        }
        int L=(degY[i]-Dy[i]+1)/2,R=(degY[i]+Dy[i])/2;
        if(L>R)failed();
        AddEdgE(Ly[i],Ry[i],L,R,0);
    }
    addedge(T,S,inf,0);
    for(int i=1;i<=T;++i)
        if(dlt[i]>0)addedge(0,i,dlt[i],0);else
            if(dlt[i]<0)addedge(i,TT,-dlt[i],0);
    while(MCMF());
    for(int i=head[0];i;i=e[i].nxt)
        if(e[i].cap)failed();
    cout<<ans<<'\n';
    for(int i=1;i<=n;++i)
        if(e[Id[i]].cap^tag)cout.put('r');else cout.put('b');
    cout<<'\n';
    return 0;
}
Powered by Hexo
Theme - Material