欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Codeforces 704D. Captain America 上下界网络流(TLE)

程序员文章站 2022-06-10 14:46:20
...

题解:

首先想想怎么建图。对于r<b,那么显然要最大化染红色的数量,反之同理。于是建两排点,一排表示行,一排表示列,源点向每个表示行的点连一条有上下界的边,每个表示列的点向汇点连一条有上下界的边,表示限制,对于一个点(x,y)就在代表x行,y列的边之间连一条流量为1的边,表示染色,然后最大流就是最多能染多少。
上下界怎么解决呢?
Codeforces 704D. Captain America 上下界网络流(TLE)我TLE了,留坑。

代码:

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define pa pair<int,int>
const int Maxn=210000;
const LL inf=(1LL<<60);
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    return x*f;
}
int n,m,R,B,st,ed,S,T,S1,T1,SS,TT,tot=0,num[Maxn];
vector<int>limx[Maxn],limy[Maxn];
struct Point{int x,y;}p[Maxn];
map<int,int>mp[2];int cntx=0,cnty=0;
struct Edge{int y,next;LL d;}e[Maxn<<3];
int last[Maxn],len=1;
void ins(int x,int y,LL d)
{
    int t=++len;
    e[t].y=y;e[t].d=d;
    e[t].next=last[x];last[x]=t;
}
void addedge1(int x,int y,LL d){ins(x,y,d);ins(y,x,0);}
void addedge2(int x,int y,LL L,LL R)
{
    addedge1(SS,y,L);
    addedge1(x,TT,L);
    if(R!=L)addedge1(x,y,R-L);
}
int h[Maxn];
bool bfs()
{
    memset(h,0,sizeof(h));h[st]=1;
    queue<int>q;q.push(st);
    while(!q.empty())
    {
        int x=q.front();q.pop();
        for(int i=last[x];i;i=e[i].next)
        {
            int y=e[i].y;
            if(!h[y]&&e[i].d>0)h[y]=h[x]+1,q.push(y);
        }
    }
    return h[ed];
}
LL dfs(int x,LL f)
{
    if(x==ed)return f;
    LL s=0,t;
    for(int i=last[x];i;i=e[i].next)
    {
        int y=e[i].y;
        if(h[y]==h[x]+1&&e[i].d>0&&s<f)
        {
            t=dfs(y,min(f-s,e[i].d));
            s+=t;e[i].d-=t;e[i^1].d+=t;
        }
    }
    if(!s)h[x]=0;
    return s;
}
int totx[Maxn],toty[Maxn];
int main()
{
    bool flag=false;
    n=read(),m=read(),R=read(),B=read();
    if(R>B)swap(R,B),flag=true;
    for(int i=1;i<=n;i++)
    {
        int x=read(),y=read();
        if(!mp[0][x])mp[0][x]=++cntx;
        if(!mp[1][y])mp[1][y]=++cnty;
        p[i].x=mp[0][x],p[i].y=mp[1][y];
        totx[p[i].x]++;toty[p[i].y]++;
    }
    for(int i=1;i<=m;i++)
    {
        int t=read(),l=read(),d=read();
        if(t==1)
        {
            int o=mp[0][l];
            if(o)limx[o].push_back(d);
        }
        else
        {
            int o=mp[1][l];
            if(o)limy[o].push_back(d);
        }
    }
    tot=cntx+cnty;
    S=++tot;T=++tot;
    S1=++tot;T1=++tot;
    SS=++tot;TT=++tot;
    addedge1(S,S1,n);addedge1(T1,T,n);
    for(int i=1;i<=cntx;i++)
    {
        LL mnd=inf;
        for(int j=0;j<limx[i].size();j++)mnd=min(mnd,(LL)limx[i][j]);
        if(mnd==inf)addedge1(S1,i,totx[i]);
        else
        {
            mnd=min(mnd,(LL)totx[i]);
            LL least=(totx[i]-mnd+1)/2,most=(totx[i]+mnd)/2;
            if(least>most)return puts("-1"),0;
            addedge2(S1,i,least,most);
        }
    }
    for(int i=1;i<=cnty;i++)
    {
        LL mnd=inf;
        for(int j=0;j<limy[i].size();j++)mnd=min(mnd,(LL)limy[i][j]);
        if(mnd==inf)addedge1(i+cntx,T1,toty[i]);
        else
        {
            mnd=min(mnd,(LL)toty[i]);
            LL least=(toty[i]-mnd+1)/2,most=(toty[i]+mnd)/2;
            if(least>most)return puts("-1"),0;
            addedge2(i+cntx,T1,least,most);
        }
    }
    for(int i=1;i<=n;i++)
    addedge1(p[i].x,p[i].y+cntx,1),num[i]=len;
    addedge1(T,S,inf);
    st=SS,ed=TT;
    LL tmp=0,pd=0;
    while(bfs())dfs(st,inf);
    tmp=e[len].d;
    for(int i=last[SS];i;i=e[i].next)pd+=e[i].d;
    if(pd)return puts("-1");
    e[len^1].d=e[len].d=0;last[SS]=0;
    st=S,ed=T;
    while(bfs())tmp+=dfs(st,inf);
    printf("%lld\n",tmp*(LL)(R)+(n-tmp)*(LL)(B));
    for(int i=1;i<=n;i++)
    {
        int o;
        if(!e[num[i]^1].d)o=1;else o=0;
        if(flag)o^=1;
        if(o)putchar('r');
        else putchar('b');
    }
}