题解 CF786E 【ALT】

Rorschachindark · 2020-08-06 15:23:29 · 题解

题目传送门

题目大意

给出一个 n 个点的树，有 m 个居民，他们都非常喜欢狗，于是，每个居民要求要么给它一条狗，要么在他散步的路径上每条边都有狗。求最少需要几个狗。

n,m\le 2\times 10^4

思路

可以看出来肯定是个网络流之类的东西，那肯定是把居民和边连起边，经过思考，你发现如果对于点 i ，我们 s\to i 容量为 1 ，[l,r]\to t 容量为 1 ，i \to [l,r] 容量为 \infty，答案其实就是最小割。其中 [l,r] 表示该居民散步的路径上的边。至于为什么自己画一下图就知道了，就是你要么删居民要么删掉边。

然后你发现 n^2 条边肯定是会爆炸的，于是我们可以线段树优化建图，边数就降到了 n\log n 条，具体可以用树链剖分实现。

\texttt{Code}

#include <bits/stdc++.h>
using namespace std;

#define Int register int
#define INF 0x3f3f3f3f
#define MAXN 2000005

int n,m,top = 1,to[MAXN],wei[MAXN],cur[MAXN],nxt[MAXN],head[MAXN],fuck[MAXN];
void Add_Edge (int u,int v,int w){
    to[++ top] = v,wei[top] = w,nxt[top] = head[u],head[u] = top;
    to[++ top] = u,wei[top] = 0,nxt[top] = head[v],head[v] = top;
} 

void build (int i,int l,int r,int fuckto){
    if (l == r) return fuck[i] = l,Add_Edge (i,fuckto,1);
    int mid = (l + r) >> 1,ls = i << 1,rs = i << 1 | 1;
    Add_Edge (i,ls,INF),Add_Edge (i,rs,INF),build (ls,l,mid,fuckto),build (rs,mid + 1,r,fuckto);
}

void modify (int i,int l,int r,int tl,int tr,int d){
    if (l >= tl && r <= tr) return Add_Edge (d,i,INF);
    int mid = (l + r) >> 1,ls = i << 1,rs = i << 1 | 1;
    if (tr > mid) modify (rs,mid + 1,r,tl,tr,d);
    if (tl <= mid) modify (ls,l,mid,tl,tr,d);
}

int dep[MAXN];
bool BFS (int s,int t){
    for (Int i = 1;i <= 4 * n + m + 2;++ i) cur[i] = head[i];
    memset (dep,0x3f,sizeof (dep));
    queue <int> q;while (!q.empty()) q.pop ();dep[s] = 0,q.push (s);
    while (!q.empty()){
        int u = q.front();q.pop ();
        for (Int i = head[u];i;i = nxt[i]){
            int v = to[i],w = wei[i];
            if (dep[v] == INF && w){
                dep[v] = dep[u] + 1;
                q.push (v);
            }
        }
    }
    return dep[t] != INF;
}

int dfs (int s,int t,int lim){
    if (s == t) return lim;
    int used = 0;
    for (Int& i = cur[s];i && lim;i = nxt[i]){
        cur[s] = i;int v = to[i],w = wei[i];
        if (dep[v] == dep[s] + 1 && w){
            int del = dfs (v,t,min (lim,w));
            used += del,lim -= del,wei[i] -= del,wei[i ^ 1] += del;
        }
    }
    if (lim == 0) dep[s] = INF;
    return used;
}

int Dinic (int s,int t){
    int res = 0;
    while (BFS (s,t)) res += dfs (s,t,INF);
    return res;
}

#define PII pair<int,int>
#define MP make_pair

map <PII,int> cge;

struct FuckTree{
    int toop = 1,to[MAXN],nxt[MAXN],tur[MAXN],id[MAXN],head[MAXN];
    void Add_Edge (int u,int v){
        to[++ toop] = v,nxt[toop] = head[u],head[u] = toop;
        to[++ toop] = u,nxt[toop] = head[v],head[v] = toop;
    }
    int Index,dep[MAXN],par[MAXN],siz[MAXN],son[MAXN],top[MAXN],dfn[MAXN];
    void dfs1 (int u,int fa){
        par[u] = fa,dep[u] = dep[fa] + 1,siz[u] = 1,id[u] = cge[MP (u,fa)];
        for (Int i = head[u];i;i = nxt[i]) if (to[i] ^ fa){
            dfs1 (to[i],u),siz[u] += siz[to[i]];
            if (siz[to[i]] > siz[son[u]]) son[u] = to[i];
        }
    }
    void dfs2 (int u,int Top){
        top[u] = Top,dfn[u] = ++ Index,tur[Index] = u;
        if (son[u]) dfs2 (son[u],Top);
        for (Int i = head[u];i;i = nxt[i])
            if (to[i] != par[u] && to[i] != son[u]) dfs2 (to[i],to[i]);
    } 
    void Init (){dfs1 (1,0),dfs2 (1,1);} 
    void Modify (int u,int v,int x){
        while (top[u] ^ top[v]){
            if (dep[top[u]] < dep[top[v]]) swap (u,v);
            modify (1,1,n,dfn[top[u]],dfn[u],x),u = par[top[u]];
        }
        if (dfn[u] > dfn[v]) swap (u,v);
        if (u ^ v) modify (1,1,n,dfn[u] + 1,dfn[v],x);  
    }
}Tree;

bool vis[MAXN];
void dfs2 (int u){
    vis[u] = 1;
    for (Int i = head[u];i;i = nxt[i])
        if (wei[i] && !vis[to[i]]) dfs2 (to[i]);
}

template <typename T> inline void read (T &t){t = 0;char c = getchar();int f = 1;while (c < '0' || c > '9'){if (c == '-') f = -f;c = getchar();}while (c >= '0' && c <= '9'){t = (t << 3) + (t << 1) + c - '0';c = getchar();} t *= f;}
template <typename T,typename ... Args> inline void read (T &t,Args&... args){read (t);read (args...);}
template <typename T> inline void write (T x){if (x < 0){x = -x;putchar ('-');}if (x > 9) write (x / 10);putchar (x % 10 + '0');}

signed main(){
    read (n,m);
    for (Int i = 2,u,v;i <= n;++ i) read (u,v),Tree.Add_Edge (u,v),cge[MP (u,v)] = cge[MP (v,u)] = i - 1;Tree.Init ();
    int s = n * 4 + m + 1,t = n * 4 + m + 2;build (1,1,n,t);
    for (Int i = 1,l,r;i <= m;++ i) read (l,r),Tree.Modify (l,r,n * 4 + i),Add_Edge (s,n * 4 + i,1);
    write (Dinic (s,t)),putchar ('\n');dfs2 (s);
    vector <int> people,edge;
    for (Int i = head[s];i;i = nxt[i]) if (!vis[to[i]]) people.push_back (to[i] - 4 * n);
    for (Int i = head[t];i;i = nxt[i]) if (vis[to[i]]) edge.push_back (Tree.id[Tree.tur[fuck[to[i]]]]);
    write (people.size()),putchar (' ');for (Int i = 0;i < people.size();++ i) write (people[i]),putchar (' ');putchar ('\n');
    write (edge.size()),putchar (' ');for (Int i = 0;i < edge.size();++ i) write (edge[i]),putchar (' ');putchar ('\n');
    return 0;
}

附

checker 判断你的答案是否合法

#include <bits/stdc++.h>
using namespace std;

#define Int register int
#define MAXN 20005

template <typename T> inline void read (T &t){t = 0;char c = getchar();int f = 1;while (c < '0' || c > '9'){if (c == '-') f = -f;c = getchar();}while (c >= '0' && c <= '9'){t = (t << 3) + (t << 1) + c - '0';c = getchar();} t *= f;}
template <typename T,typename ... Args> inline void read (T &t,Args&... args){read (t);read (args...);}
template <typename T> inline void write (T x){if (x < 0){x = -x;putchar ('-');}if (x > 9) write (x / 10);putchar (x % 10 + '0');}

int n,m,vis[MAXN],dep[MAXN],toop = 1,fa[MAXN],to[MAXN],nxt[MAXN],sum[MAXN],head[MAXN],a1[MAXN],a2[MAXN],al[MAXN],ar[MAXN];
void Add_Edge (int u,int v){to[++ toop] = v,nxt[toop] = head[u],head[u] = toop;}

void dfs (int u,int par){
    fa[u] = par,dep[u] = dep[par] + 1;
    for (Int i = head[u];i;i = nxt[i]){
        int v = to[i];if (v == par) continue;
        dfs (v,u);
    }
}

void dfs2 (int u){
    for (Int i = head[u];i;i = nxt[i])
        if (to[i] != fa[u]) dfs2 (to[i]);
}

bool check (int l,int r){
    bool flag = 1;
    while (l ^ r){
        if (dep[l] < dep[r]) swap (l,r);
        if (!sum[l]) return 0;l = fa[l];
    } 
    return 1;
}

signed main(){
    read (n,m);
    for (Int i = 2,u,v;i <= n;++ i) read (u,v),a1[i - 1] = u,a2[i - 1] = v,Add_Edge (u,v),Add_Edge (v,u);
    for (Int i = 1;i <= m;++ i) read (al[i],ar[i]);dfs (1,0);
    int tot,tot1,tot2;read (tot,tot1);
    for (Int i = 1,a;i <= tot1;++ i) read (a),vis[a] = 1;
    read (tot2);for (Int i = 1,a;i <= tot2;++ i) read (a),sum[fa[a1[a]] == a2[a] ? a1[a] : a2[a]] = 1;
    for (Int i = 1;i <= m;++ i) if (!check (al[i],ar[i]) && !vis[i]) return puts ("You Fucking WA!"),0;
    puts ("Right!!!"); 
    return 0;
}

datamaker 生成数据

#include <bits/stdc++.h>
using namespace std;

#define Int register int
#define MAXN 

template <typename T> inline void read (T &t){t = 0;char c = getchar();int f = 1;while (c < '0' || c > '9'){if (c == '-') f = -f;c = getchar();}while (c >= '0' && c <= '9'){t = (t << 3) + (t << 1) + c - '0';c = getchar();} t *= f;}
template <typename T,typename ... Args> inline void read (T &t,Args&... args){read (t);read (args...);}
template <typename T> inline void write (T x){if (x < 0){x = -x;putchar ('-');}if (x > 9) write (x / 10);putchar (x % 10 + '0');}

signed main(){
    freopen ("data.in","w",stdout);
    srand (time (NULL));
    int n = rand() % 100 + 1,m = rand() % n + 1;cout << n << " " << m << endl;
    for (Int i = 2;i <= n;++ i) cout << i << " " << rand() % (i - 1) + 1 << endl;
    for (Int i = 1;i <= m;++ i) cout << rand () % n + 1 << " " << rand() % n + 1 << endl;
    return 0;
}