Codeforces 704D_codeforces#704

我写代码像cxk.jpg，因为弱智错误调了一年。
不妨设$r\le b$，我们显然希望将尽量多的点染红。
构造一个行列模型，将每行每列作为一个点，每个点作为一条边，得到一个二分图，我们令一条边被流等价于该点染红。那么根据限制，可以求出每行每列染成红色的点数目的上下界。直接求一个上下界最大流即可，额外边不满流就无解。
用dinic的话时间复杂度上界是$\mathcal{O}(n^{\frac{5}{3}})$，不过实际上跑的很快。

#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
 
using namespace std;
 
typedef long long ll;
 
struct Edge {
  int t,f,next;
  Edge() {}
  Edge(int a,int b,int c):t(a),f(b),next(c) {}
};
 
Edge e[2000000];
int head[200005],vs,vt,tot=-1;
int d[200005];
 
inline void addEdge(int x,int y,int z) {
  e[++tot]=Edge(y,z,head[x]);
  head[x]=tot;
  e[++tot]=Edge(x,0,head[y]);
  head[y]=tot;
}
 
namespace Flow {
 
int d[200005],cur[200005];
queue <int> q;
 
bool bfs() {
  while (!q.empty()) q.pop();
  memset(d,255,sizeof(d));
  d[vs]=0;cur[vs]=head[vs];
  q.push(vs);
  while (!q.empty()) {
  	int x=q.front();q.pop();
  	for(int i=head[x];i!=-1;i=e[i].next)
  	  if (e[i].f&&d[e[i].t]==-1) {
  	  	  int u=e[i].t;
  	  	  d[u]=d[x]+1;
  	  	  cur[u]=head[u];
  	  	  if (u==vt) return 1;
  	  	  q.push(u);
		}
  }
  return 0;
}
 
int dfs(int x,int a) {
  if (x==vt||!a) return a;
  int ans=0;
  for(int &i=cur[x];i!=-1;i=e[i].next)
    if (e[i].f&&d[e[i].t]==d[x]+1) {
    	int u=e[i].t;
    	int f=dfs(u,min(a,e[i].f));
    	if (f) {
    		e[i].f-=f;
    		e[i^1].f+=f;
    		ans+=f;
    		a-=f;
    		if (!a) break;
		}
	}
  return ans;
}
 
int maxflow() {
  int ans=0;
  while (bfs())
    ans+=dfs(vs,inf);
  return ans;
}
 
}
 
int id[100005];
int min1[100005],min2[100005];
int size1[100005],size2[100005];
map <int,int> rid,cid;
 
int main() {
  memset(head,255,sizeof(head));
  memset(min1,0x3f,sizeof(min1));
  memset(min2,0x3f,sizeof(min2));
  int n,m,R,B;
  scanf("%d%d%d%d",&n,&m,&R,&B);
  vs=0;vt=2*n+1;
  int sz1=0,sz2=0;
  for(int i=1;i<=n;i++) {
  	int x,y;
  	scanf("%d%d",&x,&y);
  	if (!rid.count(x)) rid[x]=++sz1;
  	if (!cid.count(y)) cid[y]=++sz2;
  	addEdge(rid[x],n+cid[y],1);
  	size1[rid[x]]++;size2[cid[y]]++;
  	id[i]=tot-1;
  }
  for(int i=1;i<=m;i++) {
  	int kind,x,y;
  	scanf("%d%d%d",&kind,&x,&y);
  	if (kind==1) {
  		if (!rid.count(x)) continue;
  		min1[rid[x]]=min(min1[rid[x]],y);
	  }
	else {
		if (!cid.count(x)) continue;
		min2[cid[x]]=min(min2[cid[x]],y);
	}
  }
  for(int i=1;i<=sz1;i++) {
  	int l=max(0,(size1[i]-min1[i]+1)>>1),r=min(size1[i],(size1[i]+min1[i])>>1);
  	if (l>r) {
  		puts("-1");
  		return 0;
	  }
	addEdge(vs,i,r-l);
	d[vs]-=l;d[i]+=l;
  }
  for(int i=1;i<=sz2;i++) {
  	int l=max(0,(size2[i]-min2[i]+1)>>1),r=min(size2[i],(size2[i]+min2[i])>>1);
  	if (l>r) {
  		puts("-1");
  		return 0;
	  }
	addEdge(n+i,vt,r-l);
	d[n+i]-=l;d[vt]+=l;
  }
  vs=2*n+2;vt=2*n+3;
  int s=0;
  for(int i=0;i<=2*n+1;i++)
    if (d[i]>0) {
    	addEdge(vs,i,d[i]);
    	s+=d[i];
	}
	else if (d[i]<0) addEdge(i,vt,-d[i]);
  addEdge(2*n+1,0,inf);
  int sum=Flow::maxflow();
  if (sum<s) {
  	puts("-1");
  	return 0;
  }
  sum=e[tot].f;
  e[tot-1].f=e[tot].f=0;
  vs=0;vt=2*n+1;
  sum+=Flow::maxflow();
  bool v=0;
  if (R>B) {
  	v=1;
  	swap(R,B);
  }
  printf("%lld\n",(ll)R*sum+(ll)B*(n-sum));
  for(int i=1;i<=n;i++) putchar(((!e[id[i]].f)^v)?'r':'b');
  printf("\n");
  return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156