CF704D Captain America

CF704D Captain America

很套路的题吧。。唯一毒瘤的地方在于不是很有源汇上下界限最大流。。

考虑把坐标离散化一下,然后 $(x,y)$ 这个点就看成 $x \to y$ 连下界 0 上界 1 的边,表示这个点是选优秀的颜色还是不优秀的。

然后对于一个限制,我们考虑这上面有 $x$ 个点,其中两种点的差不能超过 $y$ ,这种时候这条直线上能够选择的优酷的点是在一个范围内的。推下式子可以得到,下界是 $\lceil \frac{x - y}{2} \rceil$ 上界是 $\lfloor \frac{x+y}{2} \rfloor$ 。

然后跑有源汇上下界最大流就好了。每个中间的 $x \to y$ 流量为 1 就意味着这个点选择 优秀的颜色。

。。这题爆 int 感觉很无解。。最后果断 #define int long long

记住判断一下,如果下界都大于上界了,也就是说存在必然不能满足的点,直接输出 -1 就好。

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
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "bitset"
#include "queue"
using namespace std;
#define MAXN 400006
#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
#define P 998244353
typedef long long ll;
int n , m , z , q , r , b;
int A[MAXN];

struct Node {
struct Edge *firstEdge, *currEdge;
long long level, extraIn;
} N[MAXN + 2];

struct Edge {
Node *from, *to;
int cap, flow;
Edge *next, *revEdge;

Edge(Node *from, Node *to, int cap) : from(from), to(to), cap(cap), flow(0), next(from->firstEdge) {}
};

struct Dinic {
bool makeLevelGraph(Node *s, Node *t, int n) {
for (int i = 0; i < n; i++) {
N[i].level = 0;
N[i].currEdge = N[i].firstEdge;
}

std::queue<Node *> q;
q.push(s);

s->level = 1;

while (!q.empty()) {
Node *v = q.front();
q.pop();

for (Edge *e = v->firstEdge; e; e = e->next) {
if (e->flow < e->cap && !e->to->level) {
e->to->level = v->level + 1;
if (e->to == t)
return true;
else
q.push(e->to);
}
}
}

return false;
}

int findPath(Node *s, Node *t, int limit = INT_MAX) {
if (s == t)
return limit;

for (Edge *&e = s->currEdge; e; e = e->next) {
if (e->to->level == s->level + 1 && e->flow < e->cap) {
int flow = findPath(e->to, t, std::min(limit, e->cap - e->flow));
if (flow) {
e->flow += flow;
e->revEdge->flow -= flow;
return flow;
}
}
}

return 0;
}

int operator()(int s, int t, int n) {
int res = 0;
while (makeLevelGraph(&N[s], &N[t], n)) {
int flow;
while ((flow = findPath(&N[s], &N[t])) > 0) res += flow;
}

return res;
}
} dinic;

inline Edge* addEdge(int from, int to, int cap) {
N[from].firstEdge = new Edge(&N[from], &N[to], cap);
Edge* ret = N[from].firstEdge;
N[to].firstEdge = new Edge(&N[to], &N[from], 0);

N[from].firstEdge->revEdge = N[to].firstEdge;
N[to].firstEdge->revEdge = N[from].firstEdge;
return ret;
}

inline Edge* addEdge(int from, int to, int lower, int upper) {
// printf("%d %d %d %d\n",from,to,lower,upper);
int cap = upper - lower;
Edge* ret = addEdge(from, to, cap);

N[to].extraIn += lower;
N[from].extraIn -= lower;
return ret;
}

// 原图的节点编号为 [1, n]
// 超级源点、汇点会占用 0 与 n + 1
//
// 所以总节点要开 MAXN + 2
inline int flow(int s, int t, int n) {
addEdge(t, s, INT_MAX);

int S = 0, T = n + 1;

int sum = 0;
for (int i = 1; i <= n; i++) {
if (N[i].extraIn > 0) {
addEdge(S, i, N[i].extraIn);
sum += N[i].extraIn;
} else if (N[i].extraIn < 0) {
addEdge(i, T, -N[i].extraIn);
}
}

// 求可行流,满足下界
int flow = dinic(S, T, n + 2);
if (flow < sum)
return -1;

// 直接增广得到最大流
return dinic(s, t, n + 2);
}

struct dun {
int x , y;
void rd( ) { scanf("%lld%lld",&x,&y); }
} D[MAXN] ;
Edge* ec[MAXN];
vi xs , ys;
int hx[MAXN] , hy[MAXN];
int strx[MAXN] , stry[MAXN];
void solve() {
// freopen("input","r",stdin);
// freopen("ot","w",stdout);
cin >> n >> m >> r >> b;
int S = 2 * n + 1 , T = 2 * n + 2;
rep( i , 1 , n ) D[i].rd() , xs.pb( D[i].x ) , ys.pb( D[i].y );
sort( all( xs ) ) , sort( all( ys ) );
xs.resize( unique( all( xs ) ) - xs.begin() );
ys.resize( unique( all( ys ) ) - ys.begin() );
rep( i , 1 , n ) D[i].x = lower_bound( all( xs ) , D[i].x ) - xs.begin() + 1 , ++ hx[D[i].x];
rep( i , 1 , n ) D[i].y = lower_bound( all( ys ) , D[i].y ) - ys.begin() + 1 , ++ hy[D[i].y];
rep( i , 1 , n ) ec[i] = addEdge( D[i].x , D[i].y + xs.size() , 0 , 1 );
int t , l , d;
for( int i = 1 ; i <= xs.size() ; ++ i ) strx[i] = n;
for( int i = 1 ; i <= ys.size() ; ++ i ) stry[i] = n;
rep( i , 1 , m ) {
scanf("%lld%lld%lld",&t,&l,&d);
if( t == 1 ) {
int L = lower_bound( all( xs ) , l ) - xs.begin() + 1;
if( L - 1 >= xs.size() || xs[L - 1] != l ) continue;
strx[L] = min( strx[L] , d );
} else {
int L = lower_bound( all( ys ) , l ) - ys.begin() + 1;
if( L - 1 >= ys.size() || ys[L - 1] != l ) continue;
stry[L] = min( stry[L] , d );
}
}
// rep( i , 1 , n ) printf("%d %d\n",D[i].x,D[i].y);
// rep( i , 1 , xs.size() ) printf("On x %d there are %d points with strict %d\n",i,hx[i],strx[i]);
// rep( i , 1 , ys.size() ) printf("On y %d there are %d points with strict %d\n",i,hy[i],stry[i]);
rep( i , 1 , xs.size() ) {
int c = hx[i] , d = strx[i];
int l = ( c - d + 1 ) / 2 , r = ( c + d ) / 2;
if( l > r ) return puts("-1") , void();
addEdge( S , i , ( c - d + 1 ) / 2 , ( c + d ) / 2 );
}
rep( i , 1 , ys.size() ) {
int c = hy[i] , d = stry[i];
int l = ( c - d + 1 ) / 2 , r = ( c + d ) / 2;
if( l > r ) return puts("-1") , void();
addEdge( i + xs.size() , T , ( c - d + 1 ) / 2 , ( c + d ) / 2 );
}
int ans = flow( S , T , 2 * n + 2 );
char mn = ( r < b ? 'r' : 'b' ) , mx = ( r < b ? 'b' : 'r' );
int Mn = min( r , b ) , Mx = max( r , b );
long long res = 0;
if( ~ans ) {
vi re;
for( int i = 1 ; i <= n ; ++ i )
if( ec[i] -> flow )
re.pb( mn ) , res += Mn;
else re.pb( mx ) , res += Mx;
printf("%lld\n",res);
for( auto t : re ) putchar(t); puts("");
} else puts("-1");
}

signed main() {
// int T;cin >> T;while( T-- ) solve();
solve();
}
文章作者: yijan
文章链接: https://yijan.co/cf704d-captain-america/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Yijan's Blog