题目描述
Steve Rogers is fascinated with new vibranium shields S.H.I.E.L.D gave him. They're all uncolored. There are $ n $ shields in total, the $ i $ -th shield is located at point $ (x_{i},y_{i}) $ of the coordinate plane. It's possible that two or more shields share the same location.
Steve wants to paint all these shields. He paints each shield in either red or blue. Painting a shield in red costs $ r $ dollars while painting it in blue costs $ b $ dollars.
Additionally, there are $ m $ constraints Steve wants to be satisfied. The $ i $ -th constraint is provided by three integers $ t_{i} $ , $ l_{i} $ and $ d_{i} $ :
- If $ t_{i}=1 $ , then the absolute difference between the number of red and blue shields on line $ x=l_{i} $ should not exceed $ d_{i} $ .
- If $ t_{i}=2 $ , then the absolute difference between the number of red and blue shields on line $ y=l_{i} $ should not exceed $ d_{i} $ .
Steve gave you the task of finding the painting that satisfies all the condition and the total cost is minimum.
输入格式
The first line of the input contains two integers $ n $ and $ m $ ( $ 1<=n,m<=100000 $ ) — the number of shields and the number of constraints respectively.
The second line contains two integers $ r $ and $ b $ ( $ 1<=r,b<=10^{9} $ ).
The next $ n $ lines contain the shields coordinates. The $ i $ -th of these lines contains two integers $ x_{i} $ and $ y_{i} $ ( $ 1<=x_{i},y_{i}<=10^{9} $ ).
The next $ m $ lines contain the constrains. The $ j $ -th of these lines contains three integers $ t_{j} $ , $ l_{j} $ and $ d_{j} $ ( $ 1<=t_{j}<=2,1<=l_{j}<=10^{9},0<=d_{j}<=n $ ).
只有两种费用，肯定是尽量选少的那个。假设 \(r<b\)
每个点从 \(x\) 轴连向 \(y\) 轴。考虑如果一个直线有 \(a\) 个数，差要不超过 \(c\)，那么这条直线 \(r\) 的数量要在 \([\lceil\frac {a-c}2\rceil,\lfloor\frac {a+c}2\rfloor]\) 中。
从源点向 \(x\) 坐标连边，\(y\) 坐标向 汇点连边，流量是那个区间，然后对于一个点，他的 \(x\) 轴向 \(y\) 轴连一条边，跑有源汇上下界就行了。
注意特判 \(\lceil\frac {a-c}2\rceil>\lfloor\frac {a+c}2\rfloor\)
由于是二分图，复杂度 \(O(n\sqrt n)\)
#include<bits/stdc++.h>
using namespace std;
const int N=4e5+9,INF=1e9;
const char ch[]={'r','b'};
int lsh[N<<1],fl=1,n,m,k,a[N<<1],c[N<<1],v[N],e_num=1,hd[N],vhd[N],in[N],r,b,q[N],idx,t1[N],t2[N],as[N],to[N],ok[N<<3],g[N],h[N];
pair<int,int>p[N];
struct edge{
int v,nxt,f;
}e[N<<3];
void addedge(int u,int v,int f)
{
e[++e_num]=(edge){v,hd[u],f};
hd[u]=e_num;
e[++e_num]=(edge){u,hd[v],0};
hd[v]=e_num;
}
void add_edge(int u,int v,int r,int l)
{
if(l>r)
puts("-1"),exit(0);
addedge(u,v,r-l);
in[u]-=l,in[v]+=l;
ok[e_num]=l;
}
int bfs(int x,int T)
{
int l=1,r=1;
memcpy(hd,vhd,sizeof(hd));
memset(v,0,sizeof(v));
q[1]=x;
v[x]=1;
while(l<=r)
{
for(int i=hd[q[l]];i;i=e[i].nxt)
if(e[i].f&&!v[e[i].v])
v[q[++r]=e[i].v]=v[q[l]]+1;
++l;
}
return v[T];
}
int dfs(int x,int flow,int T)
{
if(x==T)
return flow;
int f;
for(int&i=hd[x];i;i=e[i].nxt)
{
if(v[e[i].v]==v[x]+1&&e[i].f&&(f=dfs(e[i].v,min(flow,e[i].f),T)))
{
e[i].f-=f,e[i^1].f+=f;
return f;
}
}
return 0;
}
int main()
{
scanf("%d%d%d%d",&n,&m,&r,&b);
if(r>b)
swap(r,b),fl=0;
for(int i=1;i<=n;i++)
scanf("%d%d",&p[i].first,&p[i].second),lsh[++idx]=p[i].first,lsh[++idx]=p[i].second;
sort(lsh+1,lsh+idx+1);
for(int i=1;i<=n;i++)
{
p[i].first=lower_bound(lsh+1,lsh+idx+1,p[i].first)-lsh;
p[i].second=lower_bound(lsh+1,lsh+idx+1,p[i].second)-lsh;
g[p[i].first]++,h[p[i].second]++;
addedge(p[i].first,p[i].second+idx,1);
to[i]=e_num;
}
for(int i=1;i<=idx;i++)
a[i]=g[i],c[i]=h[i];
for(int i=1,op,l,d,k;i<=m;i++)
{
scanf("%d%d%d",&op,&l,&d);
k=lower_bound(lsh+1,lsh+idx+1,l)-lsh;
if(lsh[k]^l)
continue;
if(op^2)
a[k]=min(a[k],d);
else
c[k]=min(c[k],d);
}
for(int i=1;i<=idx;i++)
add_edge(0,i,(g[i]+a[i])/2,(g[i]-a[i]+1)/2);
for(int i=1;i<=idx;i++)
add_edge(i+idx,2*idx+1,(h[i]+c[i])/2,(h[i]-c[i]+1)/2);
int ans=0,k,ret=0;
for(int i=0;i<=2*idx+1;i++)
{
if(in[i]<0)
addedge(i,2*idx+3,-in[i]);
else if(in[i]>0)
addedge(2*idx+2,i,in[i]),ans+=in[i];
}
addedge(2*idx+1,0,INF);
memcpy(vhd,hd,sizeof(hd));
while(bfs(2*idx+2,2*idx+3))
while(k=dfs(2*idx+2,INF,2*idx+3))
ret+=k;
if(ret^ans)
return puts("-1"),0;
ret=e[e_num].f;
e[e_num].f=e[e_num^1].f=0;
while(bfs(0,2*idx+1))
while(k=dfs(0,INF,2*idx+1))
ret+=k;
printf("%lld\n",ret*1LL*r+(n-ret)*1LL*b);
for(int i=1;i<=n;i++)
printf("%c",ch[e[to[i]].f^fl]);
}