题意

给你 \(n\) 个武器，\(m\) 个敌人，问你最多消灭多少个敌人，并输出方案。

总共有三种武器。

SQL 火箭 - 能消灭给你集合中的一个敌人 \(\sum |S| \le 100000\) ；

认知光束 - 可以消灭 \([l, r]\) 区间中的一个敌人；

OMG 火箭筒 - 消灭给你集合中的 \(0\) 个或者 \(2\) 个敌人，集合大小为 \(3\) ，且火箭筒消灭的集合互不重合。

\(n, m \le 5000\) 。

题解

现场的时候直觉告诉我是网络流，但是这个数据范围，以及 CodeForces 从不出网络流的传言，不敢刚。。

其实这题还是个网络流，因为可以看出来还是个是个二分图求最大匹配的模型（对于前两种武器来说）。

首先对于第一种武器，可以直接在二分图上暴力连边。

第二种武器，我们可以考虑线段树优化建边就行了。（就是树上的边从父亲向儿子连 \(inf\) 就行了）

第三种武器，看起来只有 \(0,2\) 两种取值很奇怪，其实我们可以把它当成有 \(0,1,2\) 三种取值。

也就是说这个点可以匹配 \(0\sim 2\) 个点。

为什么取 \(1\) 时候是对的呢？因为我们总可以在集合中找另外一个点，把原来消灭它的武器换成这个武器就行了。

然后就可以建完了，至于时间复杂度，题解给了一个 \(O(nm \log m)\) 的复杂度，其实我觉得是 \(O(flow)\) 。。

然后输出方案有些麻烦，首先考虑前两种武器，第一种武器可以直接先匹配，第二种武器我们在线段树上自底向上依次分配可行的节点就行了，这个用一个 std :: vector 作为递归函数返回值返回值比较好写。

然后考虑第三种武器，只需要对于 \(flow = 1\) 的情况再找一个匹配了的点，替换消灭的武器就行了。

总结

然后对于一些无法取值的流量，我们可以考虑先取，然后通过构造使得这个流量满足条件。

网络流输出方案的时候考虑退流会退到最开始的哪个地方就行了。

代码

#include 
    
     #define For(i, l, r) for(register int i = (l), i##end = (int)(r); i <= i##end; ++i)#define Fordown(i, r, l) for(register int i = (r), i##end = (int)(l); i >= i##end; --i)#define Set(a, v) memset(a, v, sizeof(a))#define Cpy(a, b) memcpy(a, b, sizeof(a))#define debug(x) cout << #x << ": " << (x) << endl#define DEBUG(...) fprintf(stderr, __VA_ARGS__)#define All(x) (x).begin(), (x).end()using namespace std;template
     
       inline bool chkmin(T &a, T b) {return b < a ? a = b, 1 : 0;}template
      
        inline bool chkmax(T &a, T b) {return b > a ? a = b, 1 : 0;}inline int read() {    int x(0), sgn(1); char ch(getchar());    for (; !isdigit(ch); ch = getchar()) if (ch == '-') sgn = -1;    for (; isdigit(ch); ch = getchar()) x = (x * 10) + (ch ^ 48);    return x * sgn;}void File() {#ifdef zjp_shadow    freopen ("a.in", "r", stdin);    freopen ("a.out", "w", stdout);#endif}int n, m;const int inf = 0x3f3f3f3f;template
       
        struct Dinic {    int Head[Maxn], Next[Maxm], cap[Maxm], to[Maxm], e;    Dinic() { e = 1; }    inline void add_edge(int u, int v, int flow) {        to[++ e] = v; Next[e] = Head[u]; Head[u] = e; cap[e] = flow;    }    inline void Add(int u, int v, int flow) {        add_edge(u, v, flow); add_edge(v, u, 0);    }    int S, T, dis[Maxn];    bool Bfs() {        queue
        
          Q; Q.push(S); Set(dis, 0); dis[S] = 1;        while (!Q.empty()) {            int u = Q.front(); Q.pop();            for (int i = Head[u], v = to[i]; i; v = to[i = Next[i]])                if (cap[i] && !dis[v]) dis[v] = dis[u] + 1, Q.push(v);        }        return dis[T];    }    int cur[Maxn];    int Dfs(int u, int flow) {        if (u == T || !flow) return flow;        int res = 0, f;        for (int &i = cur[u]; i; i = Next[i]) {            int v = to[i];            if (dis[v] == dis[u] + 1 && (f = Dfs(v, min(flow, cap[i])))) {                cap[i] -= f, cap[i ^ 1] += f, res += f;                if (!(flow -= f)) break;            }        }        if (!res) dis[u] = 0;        return res;    }    int Run() {        int sum_flow = 0;        while (Bfs())            Cpy(cur, Head), sum_flow += Dfs(S, inf);        return sum_flow;    }};const int N = 5050;Dinic<(int)1e5, (int)4e5> D;int tot;#define lson o << 1, l, mid#define rson o << 1 | 1, mid + 1, r#define Travel(i, u, v) for(int i = D.Head[u], v = D.to[i]; i; v = D.to[i = D.Next[i]])int ans[N], Bef;template
         
          struct Segment_Tree { int id[Maxn]; void Build(int o, int l, int r) { if (l == r) { id[o] = l; return ; } id[o] = ++ tot; int mid = (l + r) >> 1; Build(lson); Build(rson); D.Add(id[o], id[o << 1], id[o << 1] <= m ? 1 : inf); D.Add(id[o], id[o << 1 | 1], id[o << 1 | 1] <= m ? 1 : inf); } inline void Connect(int o, int l, int r, int ql, int qr, int Id) { if (ql <= l && r <= qr) { D.Add(Id, id[o], 1); return ; } int mid = (l + r) >> 1; if (ql <= mid) Connect(lson, ql, qr, Id); if (qr > mid) Connect(rson, ql, qr, Id); } vector
          
            find(int o, int l, int r) { if (l == r) return vector
           
            (); vector
            
              tmp; int mid = (l + r) >> 1; vector
             
               ls = find(lson), rs = find(rson); set_union(All(ls), All(rs), inserter(tmp, tmp.end())); Travel(i, id[o], v) if (v <= m && !D.cap[i]) tmp.push_back(v); Travel(i, id[o], v) if (D.cap[i] && v > Bef) { int cur = tmp[tmp.size() - 1]; tmp.pop_back(); ans[cur] = v - Bef; } return tmp; }};Segment_Tree
              
               << 2> T;vector
               
                 V1, V2, V3;int Ref[N], from[N], go[N];void Get_Ans() { for (int u : V1) { Travel(i, Ref[u], v) if (v <= m && D.cap[i ^ 1]) ans[v] = u; } T.find(1, 1, m); for (int u : V3) { int flow = D.cap[from[u]]; Travel(i, Ref[u], v) if (v != D.S && !D.cap[i]) ans[v] = u; if (flow == 1) Travel(i, Ref[u], v) if (v != D.S && D.cap[i]) { ans[v] = u; break; } }}int main () { File(); n = read(), m = read(); tot = m; T.Build(1, 1, m); Bef = tot; D.S = tot + n + 1; D.T = tot + n + 2; For (i, 1, m) D.Add(i, D.T, 1), go[i] = D.e - 1; For (i, 1, n) { int opt = read(); D.Add(D.S, Ref[i] = ++ tot, 1 + (opt == 2)); from[i] = D.e - 1; if (opt == 0) { int k = read(); V1.push_back(i); while (k --) D.Add(tot, read(), 1); } else if (opt == 1) { int l = read(), r = read(); V1.push_back(i); T.Connect(1, 1, m, l, r, tot); } else { int a = read(), b = read(), c = read(); V3.push_back(i); D.Add(tot, a, 1); D.Add(tot, b, 1); D.Add(tot, c, 1); } } printf ("%d\n", D.Run()); Get_Ans(); For (i, 1, m) if (ans[i]) printf ("%d %d\n", ans[i], i); return 0;}

转载于:https://www.cnblogs.com/zjp-shadow/p/9700362.html

你可能感兴趣的文章