CF#366 704D Captain America 上下界网络流

CF上的题，就不放链接了，打开太慢，直接上题面吧：

平面上有n个点, 第 i 个点的坐标为 ($X_i ,Y_i$), 你需要把每个点
染成红色或者蓝色, 染成红色的花费为 r , 染成蓝色的花费为 b .
有m个限制条件, 有两种类型, 第一种类型为$x = l_i$ 上的红点
与蓝点个数差的绝对值不超过 $d_i$, 第二种类型为$y= l_i$ 上的红
点与蓝点个数差的绝对值不超过 $d_i$.

题解：

　　表示这题真的写到失去理想，因为是第一次写带上下限的网络最大流，一开始就把建图和统计代价理解错了好多次。。。

　　首先我们可以观察到r, b是固定的，假设r比b小，那么我们就肯定要让涂红色尽可能多，这样才会更优。

　　因此我们就不用考虑这个代价了，只需要找到一个合法的方案且使得涂红色的尽可能多即可。

　　由于一个点要么涂红，要么涂蓝，因此我们并不需要求出涂蓝的个数，因为只要知道涂红的个数，涂蓝的个数自然就知道了。

　　因此现在问题就被简化为了：

　　　　二维平面上有n个点，有m个限制，要求被选中的点尽可能多。

　　对于任何一个限制，假设这条线上有num个点，那么我们可以得出被选中点的上限和下限：$[\frac{num - d}{2}, \frac{num + d}{2}]$。

　　而对于任何一个点是否被选，也可以看做有一个上限和下限$[0,1]$,即要么不选，要么选一个。
　　那么我们将行和列分别用点表示，如果有点(x, y),那么从第x行向第y列连一条[0, 1]的边.

　　对于x的限制，从s 到第x行连[下限，上限]的边。

　　然后跑带上下限的最大流就可以知道最多选多少点了。

　　如何不知道带上下限最大流怎么写请看：算法学习——带上下界网络流

　　这题的建图因为还要离散化，所以写起来十分恶心。。。。

　　代码比较冗长，建议只看思路。

　　（注意在cf上提交的时候只能用I64d,不能用lld)

 #include<bits/stdc++.h>

 using namespace std;

 #define R register int

 #define AC 500000

 #define ac 2000000

 #define inf 2139062143

 #define INF 2139062143

 #define LL long long

 int n, m, g, s, t, ss, ff, ww, tt, top1, top2, got, must;

 int cnt1, cnt2, x, head, tail, addflow;

 int Head[AC], Next[ac], belong[ac], date[ac], haveflow[ac], tot = ;

 int lim1_x[AC], lim2_x[AC], lim1_y[AC], lim2_y[AC], q[AC];

 int num1[AC], num2[AC], q1[AC], q2[AC], c[AC], have[AC], good[AC], last[AC];

 bool z[AC], flag, vis1[AC], vis2[AC];

 LL d[AC], ans, red, blue;

 struct node{

     int x, y;

 }p[AC];

 inline int read()

 {

     int x = ;char c = getchar();

     while(c > '' || c < '') c = getchar();

     while(c >= '' && c <= '') x = x *  + c - '', c = getchar();

     return x;

 }

 inline void add(int f, int w, int up, int down)

 {

     belong[tot] = f, date[++tot] = w, Next[tot] = Head[f], Head[f] = tot, haveflow[tot] = up - down, d[f] -= down;

     date[++tot] = f, Next[tot] = Head[w], Head[w] = tot, haveflow[tot] = , d[w] += down;

     if(w == tt) must += up - down;

 //    printf("%d ---> %d : %d\n", f, w, up - down);

 }

 inline void upmin(int &a, int b)

 {

     if(b < a) a = b;

 }

 inline void upmax(int &a, int b)

 {

     if(b > a) a = b;

 }

 inline int half1(int x)

 {

     int l = , r = cnt1, mid;

     while(l < r)

     {

         mid = (l + r) >> ;

         if(q1[mid] > x) r = mid - ;

         else if(q1[mid] < x) l = mid + ;

         else return mid;

     }

     if(q1[l] != x) return ;

     else return l;

 }

 inline int half2(int x)

 {

     int l = , r = cnt2, mid;

     while(l < r)

     {

         mid = (l + r) >> ;

         if(q2[mid] > x) r = mid - ;

         else if(q2[mid] < x) l = mid + ;

         else return mid;

     }

     if(q2[l] != x) return ;

     else return l;

 }

 void link(int x)

 {

     if(d[x] > ) add(ss, x, d[x], );

     else if(d[x] < ) add(x, tt, -d[x], );

 }

 #define c c_

 #define d d_

 void get_lim()

 {

     int opt, a, b;

     for(R i = ; i <= m; i ++)

     {

         opt = read(), a = read(), b = read();

         if(!a) continue;

         if(opt == )//x 的限制

         {

             a = half1(a);

             int c = (num1[a] + b) / , d = (num1[a] - b + ) / ;

             if(d > c) {puts("-1"); exit();}//,...这里需要判断

             upmin(lim1_x[a], c), upmax(lim1_y[a], d), vis1[a] = true;

         }

         else

         {

             a = half2(a);

             int c = (num2[a] + b) / , d = (num2[a] - b + ) / ;

             if(d > c) {puts("-1"); exit();}

             upmin(lim2_x[a], c), upmax(lim2_y[a], d), vis2[a] = true;

         }

     }

 }

 void pre()

 {

     n = read(), m = read(), red = read(), blue = read();

     s = n + m + , t = s + , ss = t + , tt = ss + ;

     memset(lim1_x, , sizeof(lim1_x));

     memset(lim2_x, , sizeof(lim2_x));

     for(R i = ; i <= n; i ++)

         q1[++top1] = p[i].x = read(), q2[++top2] = p[i].y = read();

     sort(q1 + , q1 + top1 + );

     sort(q2 + , q2 + top2 + );

     for(R i = ; i <= top1; i ++)

         if(q1[i] != q1[i + ]) q1[++cnt1] = q1[i];

     for(R i = ; i <= top2; i ++)

         if(q2[i] != q2[i + ]) q2[++cnt2] = q2[i];

     g = cnt1, ff = tot + ;

     for(R i = ; i <= n; i ++)

     {

         p[i].x = half1(p[i].x), p[i].y = half2(p[i].y);

         add(p[i].x, p[i].y + g, , );

         ++num1[p[i].x], ++num2[p[i].y];

     }

     ww = tot;

     get_lim();

     for(R i = ; i <= cnt1; i ++)

         if(vis1[i]) add(s, i, lim1_x[i], lim1_y[i]);

     for(R i = ; i <= cnt2; i ++)

         if(vis2[i]) add(i + g, t, lim2_x[i], lim2_y[i]);

     for(R i = ; i <= n; i ++)

     {

         if(!vis1[p[i].x])

             vis1[p[i].x] = true, add(s, p[i].x, inf, );

         if(!vis2[p[i].y])

             vis2[p[i].y] = true, add(p[i].y + g, t, inf, );

     }

     add(t, s, inf, );

     link(s), link(t);

     for(R i = ; i < s; i ++) link(i);

 }

 #undef c

 #undef d

 void bfs()

 {

     int x, now, k = flag ? t : tt;

     if(flag) memset(have, , sizeof(have));

     if(flag) memset(c, , sizeof(c));

     head = tail = ;

     q[++tail] = k, c[k] = , have[] = ;

     while(head < tail)

     {

         x = q[++head];

         for(R i = Head[x]; i; i = Next[i])

         {

             now = date[i];

             if(flag && (now == ss || now == tt)) continue;

             if(!c[now]/* && haveflow[i ^ 1]*/)

             {

                 c[now] = c[x] + ;

                 q[++tail] = now;

                 ++ have[c[now]];

             }

         }

     }

     memcpy(good, Head, sizeof(Head));

 }    

 void aru()

 {

     int k = flag ? s : ss;

     while(x != k)

     {

         //if(flag) printf("%d ---> %d\n", x, date[last[x] ^ 1]);

         haveflow[last[x]] -= addflow;

         haveflow[last[x] ^ ] += addflow;

         x = date[last[x] ^ ];

     }

     //printf("\n\n");

     if(flag) ans += addflow;

     else got += addflow;

 }

 void isap()

 {

     int now; bool done;int k = flag ? t : tt, kk = flag ? s : ss;

     addflow = inf, x = kk;

     while(c[kk] != k + )

     {

         if(x == k) aru(), addflow = inf;

         done = false;

         for(R i = good[x]; i; i = Next[i])

         {

             now = date[i];

             if(flag && (now == ss || now == tt)) continue;

             if(c[now] == c[x] -  && haveflow[i])

             {

                 upmin(addflow, haveflow[i]);

                 good[x] = i, last[now] = i;

                 x = now, done = true;

                 break;

             }

         }

         if(!done)

         {

             int go = k + ;

             for(R i = Head[x]; i; i = Next[i])

             {

                 now = date[i];

                 if(flag && (now == ss || now == tt)) continue;

                 if(haveflow[i] && c[now]) upmin(go, c[now]);

             }

             if(!(-- have[c[x]])) break;

             ++have[c[x] = go + ];

             good[x] = Head[x];

             if(x != kk) x = date[last[x] ^ ];

         }

     }

 }

 void write(bool k)

 {

     if(k)

     {

         if(red < blue) putchar('r');

         else putchar('b');

     }

     else

     {

         if(red > blue) putchar('r');

         else putchar('b');

     }

 }

 void find()

 {

     for(R i = ff; i <= ww; i += ) write(haveflow[i ^ ]);

     printf("\n");

 }

 void work()

 {

     LL k = min(red, blue), kk = max(red, blue);

     flag = true;

     if(got != must) {puts("-1"); return ;}

     bfs();

     isap();

     ans = k * ans + kk * (n - ans);

     printf("%lld\n", ans);

     find();

 }

 int main()

 {

     freopen("in.in", "r", stdin);

     pre();

     bfs();

     isap();

     work();

     fclose(stdin);

     return ;

 }

巴特西

CF#366 704D Captain America 上下界网络流

最新文章

热门文章