题意

给定一个坐标平面上的N个点，要为这些点染色，每种点可以染为两种颜色，红色花费为r，蓝色花费为b。
现在给出m个约束条件，每个条件形如：“ ti li di ”表示：
1.如果ti=1，那么要求x=li上所有点红蓝数量之差小于等于di
2.如果ti=2，那么要求y=li上所有点红蓝数量之差小于等于di
然后要你最小化花费

题解

很裸的一个上下界网络流。。
就每一列每一行开一个点就可以了
然后点就是边
原点连向行，列连向汇点
然后如果有限制的话就相当于有一个上下界
跑一个上下界最大流即可
在这里说一下上下界这个模型的构图方法：

模型构图方法

为了满足下界，我们建立一个超级原点SS，超级汇点TT
如果有一条边，x—>y，他有范围[L,R]
那么就让SS向y连一条L的边，x向TT连一条L的边
x到y是一条R-L的边
最后让T向S连一条边
然后先让SS，TT跑一次最大流
如果慢流，那么就OK
仔细想想可以知道，这样的话就相当于满足了所有的下界了
然后统计当前有多少流量
这个就是SS连向原点S的流量
然后把T到S的边删掉
然后再从S流T，这样就是最大流了

但其实我们只需要最后扫一次，看看哪一个边是不是满流，如果是，那么他就是被割了，那么就可以了

至于最后方案怎么输出，你只需要看一下这个点所代表的边是不是满流就可以了

然后我T了。。写的dinic

CODE:

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
using namespace std;
typedef long long LL;
const int MAX=(1<<28);
const int N=100010*2;
const int M=N*13;
int n,m;
int cnt1=0,cnt2=0;//两种东西的个数
struct node
{int x,y;//两个点 
}s[N];
map<int,int> mp[2];
int o[N],t[N];//这个点上面有多少个东西 
int S,T,SS,TT;
struct qq
{int x,y,last,z;
}e[M],E[M];int num,last[N];
void init1 (int x,int y,int z)
{e[++num].x=x;e[num].y=y;e[num].z=z;e[num].last=last[x];last[x]=num;
}
void init (int x,int y,int z){
   /*printf("OZY:%d %d %d\n",x,y,z);*/init1(x,y,z);init1(y,x,0);}
int lalal=0;//最大流 
int h[N];
bool bt (int st,int ed)
{
// memset(h,-1,sizeof(h));for (int u=0;u<=TT;u++) h[u]=-1;h[st]=1;queue<LL> q;q.push(st);while (!q.empty()){int x=q.front();q.pop();for (int u=last[x];u!=-1;u=e[u].last){int y=e[u].y;if (e[u].z>0&&h[y]==-1){h[y]=h[x]+1;q.push(y);}}}return h[ed]!=-1;
}
int dfs (int x,int ed,int f)
{if (x==ed) return f;int s1=0;for (int u=last[x];u!=-1;u=e[u].last){int y=e[u].y;if (e[u].z>0&&h[y]==h[x]+1&&s1<f){int lalal=dfs(y,ed,min(e[u].z,f-s1));s1+=lalal;e[u].z-=lalal;e[u^1].z+=lalal;}}if (s1==0) h[x]=-1;return s1;
}
int belong[M];
void dinic (int st,int ed)
{while (bt(st,ed))  lalal=lalal+dfs(st,ed,MAX);
}
bool check ()
{int x=SS;for (int u=last[x];u!=-1;u=e[u].last)if (e[u].z>0) return false;return true;
}
int ans[N];
int main()
{
// freopen("my.out","w",stdout);int r,b;num=1;memset(last,-1,sizeof(last));scanf("%d%d%d%d",&n,&m,&r,&b);for (int u=1;u<=n;u++){scanf("%d%d",&s[u].x,&s[u].y);if (mp[0][s[u].x]==0) mp[0][s[u].x]=++cnt1;if (mp[1][s[u].y]==0) mp[1][s[u].y]=++cnt2;s[u].x=mp[0][s[u].x];s[u].y=mp[1][s[u].y];}S=0;T=cnt1+cnt2+1;SS=T+1;TT=SS+1;for (int u=1;u<=n;u++){init(s[u].x,s[u].y+cnt1,1);belong[num-1]=u;o[s[u].x]++;o[cnt1+s[u].y]++;}memset(t,63,sizeof(t));for (int u=1;u<=m;u++){int tt,l,d;scanf("%d%d%d",&tt,&l,&d);if (mp[tt-1].find(l)==mp[tt-1].end()) continue;l=mp[tt-1][l]+(tt-1)*cnt1;t[l]=min(t[l],d);}for (int u=1;u<=cnt1+cnt2;u++){t[u]=min(t[u],o[u]);int L=(o[u]-t[u])/2+(o[u]-t[u])%2;int R=(o[u]+t[u])/2;//printf("\nYES:%d %d %d %d %d\n",u,t[u],o[u],L,R);if (L>R) {
   printf("-1");return 0;}if (u<=cnt1){init(SS,u,L);init(S,TT,L);init(S,u,R-L);}else{init(SS,T,L);init(u,TT,L);init(u,T,R-L);}}init(T,S,MAX);dinic(SS,TT);lalal=e[last[S]].z;//printf("OZY:%d\n",lalal);if (check()==false) {
   printf("-1");return 0;}last[T]=e[last[T]].last;last[S]=e[last[S]].last;dinic(S,T);int sw=0;if (r>b) swap(r,b),sw=1;printf("%I64d\n",(LL)lalal*r+(LL)(n-lalal)*b);for (int u=1;u<=cnt1;u++){for (int i=last[u];i!=-1;i=e[i].last){if (belong[i]==0) continue;if (e[i].z==0)//这条边被割了ans[belong[i]]=sw; else ans[belong[i]]=(!sw);}}for (int u=1;u<=n;u++){if (ans[u]==0) printf("r");else printf("b");}return 0;
}