Chlience

【题解】CF 1045A Last chance
Problem传送门 >ω<题目大意:有 $n$ 个武器, $m$ 个敌人第一种武器能消灭 $k$ 个中任意一个敌...
扫描右侧二维码阅读全文
23
2018/10

【题解】CF 1045A Last chance

Problem

传送门 >ω<

题目大意:有 $n$ 个武器, $m$ 个敌人
第一种武器能消灭 $k$ 个中任意一个敌人
第二种武器能消灭 $[l,r]$ 区间中任意一个敌人
第三种武器能消灭 $a,b,c$ 中任意 $2$ 个敌人

第三种武器能选择的敌人不重合

问最多消灭多少敌人

Solution

这个题目还是比较妙的
但是放在 A 真的好么 qwq

首先考虑比较简单的第一种和第二种武器
发现就是一个二分图最大匹配

可以用匈牙利做,时间复杂度 $O(VE)$
但是发现第二种武器一多可能导致有 $n^2$ 条边,这显然是不能够接受的

因为每个点所能够选择的都是一个连续的区间,那么考虑用线段树来优化区间选择,将 $[l , r]$ 分解为 $\log n$ 段,分别向线段树上 $\log n$ 个节点连边
同时,线段树上的每个节点向左右儿子连上流量为 $INF$ 的边,这样就能保证每个节点能覆盖整个区间

那么边数被优化到了 $n \log n$ 级别,但是不能使用匈牙利算法,网络流跑就行

最后来考虑比较复杂的第三种武器
首先肯定还是搞一条流量为 2 的边限制一下
但是有可能取到不合法的流量为 1 的情况,如何处理?有上下界网络流?貌似也不行,不能处理中间断开的情况

仔细想想什么时候才会取到不合法的流量为 1 的情况呢?
因为第三种武器间并没有交集,那么肯定是被前面的第一种或者第二种占了
将这个匹配“抢”过来即可

最终的答案处理比较麻烦,因为要输出方案
首先我们要优先满足第三种武器流量为 1 的情况,将流量为 1 的变为流量为 2 的
接下来处理第一种武器单个匹配,有可能被第三种武器占用,这里要注意
最后处理第二种武器,考虑将每个还没有配对的点分配给覆盖这个点的右端点最靠左的区间就行啦!用堆来维护

这样就能愉快的 A 掉这道假的 A 题了
代码巨长还不好调 qwq

其中有各种玄学操作:用错变量, $n , m$ 弄混... 调得我...

代码

#include <bits/stdc++.h>
using namespace std;
int read() {
    int ans = 0 , flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
const int N = 5010;
const int INF = 1000000000;


struct node {
    int id , l , r;
    bool operator < (const node a) {return r < a.r;}
}a[N];
int anum;

bool cmp(node a ,node b) {
    return a.l < b.l;
}

struct heap {
    int heapcnt = 0;
    node h[N];
    void push(node x) {
        h[++ heapcnt] = x;
        int now = heapcnt;
        while(now / 2) {
            if(h[now] < h[now / 2]) {swap(h[now] , h[now / 2]); now /= 2;}
            else break;
        }
    }
    void pop() {
        h[1] = (node){0 , 0 , 0};
        h[1] = h[heapcnt];
        h[heapcnt --] = (node){0 , 0 , 0};
        int now = 1 , son = 2;
        while(son <= heapcnt) {
            if(son + 1 <= heapcnt && h[son + 1] < h[son]) ++ son;
            if(h[son] < h[now]) {
                swap(h[son] , h[now]);
                now = son; son = now * 2;
            }
            else break;
        }
    }
}q;

int n , m;

struct edge {int t , n , f;}e[400010];
int head[4 * N] , cur[4 * N] , tot = 1;

void addedge(int u , int v , int w) {
    ++ tot;
    e[tot].t = v;
    e[tot].n = head[u];
    e[tot].f = w;
    head[u] = tot;

    ++ tot;
    e[tot].t = u;
    e[tot].n = head[v];
    e[tot].f = 0;
    head[v] = tot;
}

#define L ch[x][0]
#define R ch[x][1]
#define mid ((l + r) >> 1)

int ch[4 * N][2];
int id[4 * N];//每个点代表的位置
int rt = 1 , cnt = 1;
//线段树

int s , t;
int d[4 * N];
int f[4 * N];
//网络流

int opt[N];
int ll[N] , rr[N];
//询问

int match[N];
//答案

void build(int &x , int l , int r) {
    if(!x) x = ++ cnt;
    if(l == r) {
        id[x] = l;
        return;
    }
    else {
        build(L , l , mid);
        build(R , mid + 1 , r);
        addedge(x + n * 2 , L + n * 2 , INF);
        addedge(x + n * 2 , R + n * 2 , INF);
    }
}

void add(int x , int l , int r , int ll , int rr , int u) {
    if(l >= ll && r <= rr) addedge(u , x + n * 2 , 1);
    else {
        if(mid >= ll) add(L , l , mid , ll , rr , u);
        if(mid < rr) add(R , mid +1 , r , ll , rr , u);
    }
}

void buildedge(int x , int l , int r) {
    if(l == r) addedge(x + n * 2 , t , 1);
    else {
        buildedge(L , l , mid);
        buildedge(R , mid + 1 , r);
    }
}

int dfs(int now , int flow) {
    if(now == t) return flow;
    int use = 0;
    for(int i = cur[now] ; i ; i = e[i].n) {
        cur[now] = i;
        if(e[i].f > 0 && d[e[i].t] + 1 == d[now]) {
            int tmp = dfs(e[i].t , min(e[i].f , flow - use));
            use += tmp;
            e[i].f -= tmp;
            e[i ^ 1].f += tmp;
            if(flow == use) return use;
        }
    }
    cur[now] = head[now];

    if(! -- f[d[now]])
        d[s] = 2 * n + cnt + 2;
    ++ f[ ++ d[now]];

    return use;
}


int main() {
    n = read(); m = read();
    build(rt , 1 , m);
    for(int i = 1 ; i <= n ; ++ i) {
        opt[i] = read();
        if(opt[i] == 0) {
            int k = read();
            addedge(i , i + n , 1);
            for(int j = 1 ; j <= k ; ++ j) {
                int pos = read();
                add(1 , 1 , m , pos , pos , i + n);
            }
        }
        else if(opt[i] == 1) {
            ll[i] = read(); rr[i] = read();
            addedge(i , i + n , 1);
            add(1 , 1 , m , ll[i] , rr[i] , i + n);
        }
        else {
            int a = read() , b = read() , c = read();
            addedge(i , i + n , 2);
            add(1 , 1 , m , a , a , i + n);
            add(1 , 1 , m , b , b , i + n);
            add(1 , 1 , m , c , c , i + n);
        }
    }

    s = 2 * n + cnt + 1; t = 2 * n + cnt + 2;
    
    for(int i = 1 ; i <= n ; ++ i)
        addedge(s , i , INF);
    buildedge(1 , 1 , m);

    f[0] = 2 * n + cnt + 2;
    int ans = 0;
    while(d[s] < 2 * n + cnt + 2)
        ans += dfs(s , 1 << 30);
    printf("%d\n" , ans);

    for(int i = head[t] ; i ; i = e[i].n) {
        if(e[i].f == 1)
            match[id[e[i].t - 2 * n]] = 0;
        else
            match[id[e[i].t - 2 * n]] = -1;
    }
    for(int i = 1 ; i <= n ; ++ i) {
        if(opt[i] == 2) {
            int nowflow = 0;
            for(int j = head[i + n] ; j ; j = e[j].n) {
                if(e[j].t > 2 * n && e[j].f == 0) {
                    match[id[e[j].t - 2 * n]] = i;
                    ++ nowflow;
                }
            }
            if(nowflow == 2 || nowflow == 0) continue;
            for(int j = head[i + n] ; j ; j = e[j].n) {
                if(e[j].t > 2 * n && match[id[e[j].t - 2 * n]] == 0) {
                    match[id[e[j].t - 2 * n]] = i;
                    break;
                }
            }
        }
    }
    for(int i = 1 ; i <= n ; ++ i) {
        if(opt[i] == 0) {
            for(int j = head[i + n] ; j ; j = e[j].n) {
                if(e[j].t > 2 * n && e[j].f == 0 && match[id[e[j].t - 2 * n]] == 0) {
                    match[id[e[j].t - 2 * n]] = i;
                    break;
                }
            }
        }
    }
    for(int i = 1 ; i <= n ; ++ i)
        if(opt[i] == 1)
            a[++ anum] = (node){i , ll[i] , rr[i]};

    sort(a + 1 , a + anum + 1 , cmp);
    int top = 1;
    for(int i = 1 ; i <= m ; ++ i) {
        while(top <= anum && a[top].l <= i) q.push(a[top ++]);
        while(q.heapcnt && q.h[1].r < i) {
            q.pop();
        }
        if(match[i] == 0 && q.heapcnt) {
            match[i] = q.h[1].id;
            q.pop();
        }
    }

    for(int i = 1 ; i <= m ; ++ i)
        if(match[i] != -1)
            printf("%d %d\n" , match[i] , i);
    return 0;
}
Last modification:October 30th, 2018 at 09:52 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment