bzoj D. Captain America（TLE）

題意：

平面上有 n 個點, 第 i 個點的坐标為 (Xi,Yi) ( X i , Y i ) , 你需要把每個點染成紅色或者藍色, 染成紅色的花費為 r, 染成藍色的花費為 b。有 m 個限制條件, 有兩種類型, 第一種類型為 x=li x = l i 上的紅點與藍點個數差的絕對值不超過 d, 第二種類型為 y=li y = l i 上的紅點與藍點個數差的絕對值不超過 d。

題意：

肯定是将盡量多的點染成代價較小的顔色。

将坐标離散化，對每一行，每一列開一個點。将對應的點連上，流量為1。

其它限制其實就是上下界，直接建上下界網絡流即可。

code：（TLE）

#include<queue>
#include<map>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define LL long long
using namespace std;
const int inf=<<;
struct node{
    int X,Y,num,x,y;
}p[],P[];
int n,m,R,B,numx[],numy[];
int st,ed,ST,ED,to[];
map<int,int> X,Y;
bool cmpx(node a,node b) {return a.X<b.X;}
bool cmpy(node a,node b) {return a.Y<b.Y;}
struct Node{
    int y,c,next;
}a[<<];int len=,last[];
int dx[],dy[];
int read()
{
    int x=,f=;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*+ch-'0';ch=getchar();}
    return x*f;
}
void ins(int x,int y,int c)
{
    a[++len].y=y;a[len].c=c;
    a[len].next=last[x];last[x]=len;
    a[++len].y=x;a[len].c=;
    a[len].next=last[y];last[y]=len;
}
int xnum,ynum;
void end() {puts("-1");exit();}
void build()
{
    ins(ed,st,inf);
    for(int i=;i<=n;i++) ins(P[i].x,P[i].y+xnum,),to[i]=len-;
    for(int i=;i<=xnum;i++)
    {
        if(dx[i]==inf) ins(st,i,numx[i]);
        else
        {
            int l=max((numx[i]-dx[i]+)>>,),r=min((numx[i]+dx[i])>>,numx[i]);
            if(l>r) end();
            ins(st,i,r-l);ins(ST,i,l);ins(st,ED,l);
        }
    }
    for(int i=;i<=ynum;i++)
    {
        if(dy[i]==inf) ins(i+xnum,ed,numy[i]);
        else
        {
            int l=max((numy[i]-dy[i]+)>>,),r=min((numy[i]+dy[i])>>,numy[i]);
            if(l>r) end();
            ins(i+xnum,ed,r-l);ins(ST,ed,l);ins(i+xnum,ED,l);
        }
    }
}
int h[];
queue<int> q;
int findflow(int x,int ed,int f)
{
    if(x==ed) return f;
    int ans=,t;
    for(int i=last[x];i;i=a[i].next)
    {
        int y=a[i].y;
        if(ans<f&&h[y]==h[x]+&&a[i].c)
        {
            ans+=(t=findflow(y,ed,min(a[i].c,f-ans)));
            a[i].c-=t;a[i^].c+=t;
        }
    }
    if(ans==) h[x]=;
    return ans;
}
bool bt_h(int st,int ed)
{
    memset(h,,sizeof(h));h[st]=;
    q.push(st);
    while(!q.empty())
    {
        int x=q.front();q.pop();
        for(int i=last[x];i;i=a[i].next)
        {
            int y=a[i].y;
            if(h[y]==&&a[i].c) h[y]=h[x]+,q.push(y);
        }
    }
    return h[ed]!=;
}
int dinic(int st,int ed)
{
    int ans=;
    while(bt_h(st,ed)) ans+=findflow(st,ed,inf);
    return ans;
}
int flag=false;
int main()
{
    n=read();m=read();R=read();B=read();
    for(int i=;i<=n;i++) p[i].X=read(),p[i].Y=read(),p[i].num=i;
    sort(p+,p+n+,cmpx);xnum=;
    memset(numx,,sizeof(numx));
    for(int i=;i<=n;i++)
    {
        if(i==||p[i].X!=p[i-].X) xnum++;
        X[p[i].X]=xnum;P[p[i].num].x=xnum;
        numx[xnum]++;
    }
    sort(p+,p+n+,cmpy);ynum=;
    memset(numy,,sizeof(numy));
    for(int i=;i<=n;i++)
    {
        if(i==||p[i].Y!=p[i-].Y) ynum++;
        Y[p[i].Y]=ynum;P[p[i].num].y=ynum;
        numy[ynum]++;
    }
    st=xnum+ynum+;ed=st+;ST=ed+;ED=ST+;
    for(int i=;i<=xnum;i++) dx[i]=inf;
    for(int i=;i<=ynum;i++) dy[i]=inf;
    for(int i=;i<=m;i++)
    {
        int op,l,d;op=read(),l=read(),d=read();
        if(op==) {int x=X[l];if(x) dx[x]=min(dx[x],d);}
        if(op==) {int y=Y[l];if(y) dy[y]=min(dy[y],d);}
    }
    build();
    dinic(ST,ED);int ans,tot=;
    ans=a[].c;
    for(int i=last[ST];i;i=a[i].next) tot+=a[i].c;
    a[].c=a[].c=;
    if(tot) end();
    ans+=dinic(st,ed);
    if(R>B) swap(R,B),flag=true;
    printf("%lld\n",(LL)R*(LL)ans+(LL)B*(LL)(n-ans));
    for(int i=;i<=n;i++) putchar((flag&&a[to[i]].c)||(!flag&&!a[to[i]].c)?'r':'b');
}