题目大意

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

Data Constraint
N,M≤100000

题解

假设r<b（反过来交换就好）
构造一个二分图，每条垂直于X轴的直线作为一个顶点放在二分图左边，每条垂直于Y轴的直线作为一个顶点放在二分图右边。假如有一个点(x,y)我们就从左边的x向右边的y连一条边，如果这个点选红色我们就把这条边染为1，否则是0。那么一个约束实际上就是要求一个顶点连出去的所有1边和0边之差小于等于di。
不妨设二分图中的一个顶点i一共连出去qi条边，所有约束中最小值为ei，1边有ri条。
易得
记
现在在新增一个源点S和汇点T。
S向每个x连一条流量为[Lx,Rx]的边，每个y向T连一条[Ly,Ry]的边。对于没有约束的顶点，我们可以人为地添加一个约束来方便连边。中间那些边的流量就设为1。
如果没有可行流，那么就一定是无解。因为r<b，所以我们要最大化红点的数量，S−>T跑一遍最大流就是我们的答案。

时间复杂度：O(M+Nsqrt(N))

---

上下界网络流

这题用到了上下界网络流，我就顺便写一下上下界网络流的简单处理方法。
新增一个超级源SS和一个超级汇TT。假设我们现在有一条边(u,v)，流量限制为[L,R]，我们想让有下界的网络流转化成没有下界的网络流模型，怎么做呢？如果我们能强制将下界那么多的流量流过去就好了。具体连边如下：

• (SS,v)流量为L
• (u,TT)流量为R
• (u,v)流量为R−L
• (T,S)流量为+∞

这样连边就能保证流量强制流下界的流量。

可行流

从SS出发，到TT跑一遍最大流，如果最终SS所有的出边都流满了，就说明找到了一个满足下界的可行流。

最大流

求完可行流之后，把辅助建图的SS和TT以及(T,S)都删去，再从S到T跑一遍最大流。

SRC

#include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> #include<map> using namespace std ;#define N 100000 + 10 #define M 1000000 + 10 typedef long long ll ; const int inf = 0x7FFFFFFF ; struct Point {int x , y ; } P[N] ;map < int , int > from[2];bool flag = 0 , bz[M] ; int Node[2*M] , Next[2*M] , C[2*M] , Head[M] , tot = 1 ; int vh[M] , h[M] , di[M] , Rec[2*M] ; int Q[M] , E[M] , ans[N] ; int n , m , r , b ; int S , T , SS , TT ; int MaxFlow , num ;bool cmp( Point a , Point b ) { return a.x < b.x || ( a.x == b.x && a.y < b.y ); }void link( int u , int v , int w ) {Node[++tot] = v , Next[tot] = Head[u] , C[tot] = w , Head[u] = tot ;Node[++tot] = u , Next[tot] = Head[v] , C[tot] = 0 , Head[v] = tot ; }int SAP( int x , int aug ) {int use = 0 ;if ( x == T ) return aug ;for (int p = di[x] ; p ; p = Next[p] ) {if ( h[x] != h[Node[p]] + 1 || C[p] <= 0 || bz[Node[p]] ) continue ;di[x] = p ;int ret = SAP( Node[p] , min( aug - use , C[p] ) ) ;C[p] -= ret ;C[p^1] += ret ;use += ret ;if ( h[S] > num || aug == use ) return use ;}if ( -- vh[h[x]] == 0 ) { h[S] = num + 1 ; return use ; }h[x] ++ ;vh[h[x]] ++ ;di[x] = Head[x] ;return use ; }void Flow( int u , int v ) {S = u , T = v ;memset( h , 0 , sizeof(h) ) ;memset( vh , 0 , sizeof(vh) ) ;memcpy( di , Head , sizeof(di) ) ;vh[0] = num = v + 1 ;while ( h[S] <= num ) MaxFlow += SAP( S , inf ) ;S = 0 , T = num - 3 ; }bool Impossible() {for (int p = Head[SS] ; p ; p = Next[p] ) if ( C[p] ) return 1 ;return 0 ; }int main() {scanf( "%d%d" , &n , &m ) ;scanf( "%d%d" , &r , &b ) ;int Cnt1 = 0 , Cnt2 = 0 ;for (int i = 1 ; i <= n ; i ++ ) {scanf( "%d%d" , &P[i].x , &P[i].y ) ;if ( !from[0][P[i].x] ) from[0][P[i].x] = ++ Cnt1 ;if ( !from[1][P[i].y] ) from[1][P[i].y] = ++ Cnt2 ;P[i].x = from[0][P[i].x] ;P[i].y = from[1][P[i].y] ;}S = 0 , T = Cnt1 + Cnt2 + 1 ;SS = T + 1 , TT = T + 2 , num = TT + 1 ;for (int i = 1 ; i <= n ; i ++ ) {link( P[i].x , Cnt1 + P[i].y , 1 ) ;Q[P[i].x] ++ , Q[Cnt1+P[i].y] ++ ;Rec[tot-1] = i ;}memset( E , 63 , sizeof(E) ) ;for (int i = 1 ; i <= m ; i ++ ) {int t , l , d ;scanf( "%d%d%d" , &t , &l , &d ) ;if ( from[t-1].find(l) == from[t-1].end() ) continue ;l = from[t-1][l] + (t - 1) * Cnt1 ;E[l] = min( E[l] , d ) ;}for (int i = 1 ; i < T ; i ++ ) {E[i] = min( E[i] , Q[i] ) ;int L = (Q[i] - E[i]) / 2 + (Q[i] - E[i]) % 2 ;int R = (Q[i] + E[i]) / 2 ;if ( L > R ) { printf( "-1\n" ) ; return 0 ; }if ( i <= Cnt1 ) {link( SS , i , L ) ;link( S , TT , L ) ;link( S , i , R - L ) ;} else {link( SS , T , L ) ;link( i , TT , L ) ;link( i , T , R - L ) ;}}link( T , S , inf ) ;Flow( SS , TT ) ;MaxFlow = C[Head[S]] ;if ( Impossible() ) { printf( "-1\n" ) ; return 0 ; }Head[S] = Next[Head[S]] , Head[T] = Next[Head[T]] ;bz[SS] = bz[TT] = 1 ;Flow( S , T ) ;if ( r > b ) swap( r , b ) , flag = 1 ;printf( "%I64d\n" , (ll)MaxFlow * r + (ll)(n - MaxFlow) * b ) ;for (int i = 1 ; i <= Cnt1 ; i ++ ) {for (int p = Head[i] ; p ; p = Next[p] ) {if ( !Rec[p] ) continue ;if ( !C[p] ) ans[Rec[p]] = flag ;else ans[Rec[p]] = !flag ;}}for (int i = 1 ; i <= n ; i ++ ) {if ( ans[i] == 0 ) printf( "r" ) ;else printf( "b" ) ;}return 0 ; }

以上.

总结

以上是生活随笔为你收集整理的Codeforces 704D Captain America的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。