首页 > 其他分享 >CF786E ALT 题解

CF786E ALT 题解

时间:2023-07-19 16:03:36浏览次数:42  
标签:cnt return int 题解 u1 u2 ALT id CF786E

为什么你们第一眼都能想到最小割,我第一眼都只能想到费用流。

为什么你们的做法都这么短,我一写就是 \(5KB\)。

费用流有一个基本矛盾,就是守卫只需拥有一只狗和每一个人都需要守卫有狗的基本矛盾。由于需求与供给不平衡,所以流量不好确定。如果有人费用流过了来长沙火车站,疯狂星期四我V你50。

由于最小,我们想到最小割。我们想要两种割边,一种割树上的边,一种割人。

因此我们这么构造:对于树上每条边,我们建立一个入点一个出点,源点朝入点连边,流量为 \(1\),出点向汇点连边,流量为 \(inf\)(只需要割入点就行)。

对于每个人走过的路径 \([l,r]\) (经过树链剖分处理后变为一个区间),我们将区间里的点各自分成两个点之后再分别连到一个新点上,再把两个新点连起来,流量为 \(1\),代表一个人。

你发现了区间连边的操作,于是可以线段树优化建图。

提供样例一的完整建图,其中 \(1\) 为源点,\(2\) 为汇点:

略微卡常。

#include <bits/stdc++.h>
#define F(i, n) for (int i = 1; i <= n; ++i)
#define ll long long
using namespace std;
const ll N = 1e6 + 5, INF = 5e7;

template<typename T> bool chkmax(T &a, T b) { return a < b ? (a = b, 1) : 0; }
template<typename T> bool chkmin(T &a, T b) { return a > b ? (a = b, 1) : 0; }
template<typename T> T read() { T a;cin >> a;return a; }

inline int read() {
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') {
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*f;
}


int n, m, s, t;

template<const int M>
struct graph {
  int st[M], nx[M * 6], to[M * 6], cur[M], cnt = 1;
  int id[M * 6];
  int val[M * 6];
  void add(int u, int v, int w, int i) {
    to[++cnt] = v;val[cnt] = w;nx[cnt] = st[u];st[u] = cnt;
    id[cnt] = i;
  }
};
#define go(g, u, v, w) for (int i = g.cur[u], v = g.to[i], w = g.val[i]; i; i = g.nx[i], v = g.to[i], w = g.val[i])

int cnt;
graph<N> g;
namespace Graph {
  void add(int u, int v, int w, int id) {
    g.add(u, v, w, id);
    g.add(v, u, 0, 0);
  }
  int lev[N];
  bool bfs(int s, int t) {
    for (int i = 1; i <= cnt; ++i) lev[i] = -1;
    lev[s] = 0;
    for (int i = 1; i <= cnt; ++i) g.cur[i] = g.st[i];
    queue<int> q;q.push(s);
    while (!q.empty()) {
      int u = q.front();q.pop();
      go(g, u, v, w) {
	if (w > 0 && lev[v] == -1) 
	  lev[v] = lev[u] + 1, q.push(v);
      }
    }
    return lev[t] != -1;
  }
  int dfs(int u, int flow, int t) {
    if (u == t) return flow;
    int res = flow;
    for (int i = g.cur[u]; i && res; i = g.nx[i]){
      int v = g.to[i], w = g.val[i];
      g.cur[u] = i;
      if (w > 0 && lev[v] == lev[u] + 1) {
	int c = dfs(v, min(w, res), t);res -= c;
	g.val[i] -= c;g.val[i ^ 1] += c;
      }
    }
    return flow - res;
  }
  int dinic(int s, int t) {
    int ans = 0;
    while (bfs(s, t)) {
      int p = dfs(s, INF, t);
      ans += p;
    }
    return ans;
  }
}
using Graph::add;
using Graph::dinic;

vector<tuple<int, int>> tree[N];
long long dfn[N];
int siz[N], son[N], top[N], dep[N], fa[N], pos[N], I[N];
namespace pou {
  int tot = 0;
  void findSon(int u, int F) {
    siz[u] = 1;fa[u] = F;
    int v, id;
    for (auto p : tree[u]) {
      tie(v, id) = p;
      if (v == F) continue;
      I[v] = id;
      dep[v] = dep[u] + 1;
      findSon(v, u);
      siz[u] += siz[v];
      if (siz[v] > siz[son[u]]) son[u] = v;
    }
    return ;
  }
  void mark(int u, int fa, int to) {
    int v, id;
    if (u != 1) {
      dfn[u] = ++tot;
      pos[tot] = u;
    }
    top[u] = to;
    if (son[u]) mark(son[u], u, to);
    for (auto p : tree[u]) {
      tie(v, id) = p;
      if (v == fa || v == son[u]) continue;
      mark(v, u, v);
    }
  }
}

int upId[N], dwId[N], upSon[N][2], dwSon[N][2], upRt, dwRt;
tuple<int, int> build(int l, int r) {
  if (l == r) {
    upId[l] = ++cnt;
    dwId[l] = ++cnt;
    return tie(upId[l], dwId[l]);
  }
  int mid = (l + r) >> 1;
  int u1 = ++cnt;
  int u2 = ++cnt;
  tie(upSon[u1][0], dwSon[u2][0]) = build(l, mid);
  tie(upSon[u1][1], dwSon[u2][1]) = build(mid + 1, r);
  
  add(upSon[u1][0], u1, INF, 0);
  add(upSon[u1][1], u1, INF, 0);
  add(u2, dwSon[u2][0], INF, 0);
  add(u2, dwSon[u2][1], INF, 0);
  
  return tie(u1, u2);
}
int v1, v2;
void lian(tuple<int, int> u, int l, int r, int fl, int fr) {
  int u1, u2; tie(u1, u2) = u;
  if (fl <= l && r <= fr) {
    add(u1, v1, INF, 0);
    add(v2, u2, INF, 0);
    return ;
  }
  int mid = (l + r) >> 1;
  if (mid >= fl) lian(tie(upSon[u1][0], dwSon[u2][0]), l, mid, fl, fr);
  if (mid < fr) lian(tie(upSon[u1][1], dwSon[u2][1]), mid + 1, r, fl, fr);
}
void jump(int u1, int u2){
  while (top[u1] != top[u2]) {
    if (dep[top[u1]] < dep[top[u2]]) swap(u1, u2);
    if (top[u1] == 1) {
      lian(tie(upRt, dwRt), 1, n - 1, dfn[son[top[u1]]], dfn[u1]);
    }
    else {
      lian(tie(upRt, dwRt), 1, n - 1, dfn[top[u1]], dfn[u1]);
    }
    u1 = fa[top[u1]];
  }
  if (u1 == u2) return ;
  if (dep[u1] > dep[u2]) swap(u1, u2);
  if (dfn[son[u1]] <= dfn[u2]) lian(tie(upRt, dwRt), 1, n - 1, dfn[son[u1]], dfn[u2]);
}

bool vis[N];
void dfs(int u) {
  vis[u] = 1;
  go(g, u, v, w) {
    if (w == 0 || vis[v]) continue;
    dfs(v);
  }
}

int main(){
  freopen("text.in", "r", stdin);

  int u, v;
  dfn[0] = INF;
  s = ++cnt;t = ++cnt;
  n = read(), m = read();

  int pd = 1;
  F(i, n - 1) {
    u = read(), v = read();
    tree[u].push_back(tie(v, i));
    tree[v].push_back(tie(u, i));
  }
  pou::findSon(1, 0);
  pou::mark(1, 0, 1);

  tie(upRt, dwRt) = build(1, n - 1);

  F(i, n - 1) {
    add(s, upId[i], 1, I[pos[i]]);
    add(dwId[i], t, INF, 0);
  }

  F(i, m) {
    u = read(), v = read();
    v1 = ++cnt; v2 = ++cnt;
    add(v1, v2, 1, i + n);
    jump(u, v);
  }
  
  printf("%d\n", dinic(s, t));
  dfs(s);
  vector<int> edge, peo;
  for (int i = g.st[s]; i; i = g.nx[i]) {
    if (vis[g.to[i]] == false && g.val[i] == 0) edge.push_back(g.id[i]);
  }
  for (int i = 2; i <= cnt; ++i) {
    for (int j = g.st[i]; j; j = g.nx[j]) {
      if (vis[i] != vis[g.to[j]] && g.id[j] > n && g.val[j] == 0) {
	peo.push_back(g.id[j] - n);
      }
    }
  }
  printf("%ld ", peo.size());
  for (auto i : peo) printf("%d ", i);
  puts("");
  printf("%ld ", edge.size());
  for (auto i : edge) printf("%d ", i);
  
  return 0;
}

标签:cnt,return,int,题解,u1,u2,ALT,id,CF786E
From: https://www.cnblogs.com/closureshop/p/CF786E.html

相关文章

  • [SDOI2010] 代码拍卖会 题解
    [SDOI2010]代码拍卖会题解题目描述一个\(n,n\le10^{18}\)位数,仅由\(1\sim9\)组成,后一位数字一定大于等于前一位数字。求这些数中可以被\(m,m\le500\)整除的有多少,对\(999911659\)取模。解析这个数一定形如\(112334455677788999\)可以把它拆成\[\begin{aligned}......
  • 黑群晖NAS7.0+安装问题解决经验分享
    感谢网上各种帖子及分享,为大家提供一个解决思路,机器配置多种多样,解决办法也仅供参考;1、引导后,无法找到群晖  遇到无法找到群晖的情况,首先要排除引导不兼容的问题。在bios中分别设置传统引导模式和UEFI引导模式尝试启动试下。最新版7.0.1的引导文件是两种启动方式都支持的,理......
  • 题解 [USACO18JAN] MooTube G
    题目链接可以发现,对于一个固定的\(k\),所有边权小于\(k\)的边对答案是没有贡献的,因为一条边的相关性是最小相关性,这也意味着我们不能从\(<k\)的边到达其他的点。由于本题有多组询问,所以对于没有用的边,将其看做被删除,有用的边,将其看做被插入。考虑到本题实际上要维护连通块......
  • 洛谷 P1122 最大子树和 题解
    一道入门的树形DP。首先我们对于数据进行有序化处理,这便于我们利用数据结构特点(可排序性)来发觉数据性质(有序、单调、子问题等等性质),以便于后续的转化、推理和处理。有序化可以“转化和创造”性质首先将视角从无根树切换为有根树,这样我们就可以得到一个带有最优子结构、无后效性......
  • HDU 5492 Find a path 题解
    Description在矩阵中,找一条到从\((1,1)\)到\((n,m)\)(只能向上,右走)的路径,使路径上方差最小。输出方差平方乘\(n+m-1\)的结果。对于所有数据,\(1\leqn,m,A_{i,j}\leq30\)。Solution设路径上的数为\(A_{1},A_{2},A_{3},\cdots,A_{n+m-1}\),\(\overline{A}\)为其平均数,则答......
  • 题解 序列合并
    题目链接首先不难想到,最小数的一定是\(a_1+b_1\),次小的数是\(a_1+b_2\)和\(a_2+b_1\)中小的。得出结论,若\(a_i+b_j\)是第\(k\)小,那么\(a_{i+1}+b_j\)和\(a_i+b_{j+1}\)有可能成为第\(k+1\)小。这是一个很优秀的性质,这意味着我们可以通过最小值推出次小值,再通过......
  • “范式杯”2023牛客暑期多校训练营1 蒻蒟题解
    A.AlmostCorrect题意:给定一个01串,要求构造一系列排序操作(xi,yi),使得经过这些排序操作后可以使与给定01串等长的所有其他01串完全排好序,而给定的01串无法完全排好序Solution构造题我们考虑到对0和1的位置进行统计,统计得出最左边的1的位置为l,最右边的0的位置为r我们进行三次......
  • 【SP21463 题解】
    Descirption给定\(n\timesm\)的矩阵,求最大子矩阵的面积满足每一行每一列都构成等差数列。Solution我们另\(up_{i,j}\)表示最小的\(k\)满足\((i,k),(i,k+1),\cdots,(i,j)\)构成等差数列,可以用\(\mathcalO(nm)\)求出。对于一个矩阵的左上角\((a,b)\),右下......
  • P6227 [BalticOI 2019 Day1] 山谷
    P6227[BalticOI2019Day1]山谷Description给一棵树,一个根,一些特殊补给点,一些询问。求解如下问题:断掉一条边\(u\tov\),这样以后你能否从给定的\(R_i\)走到根,若能输出escaped。不能到达根且不能到达任何一个特殊补给点输出oo。若不能到达根但可以到达特殊补给点输出边权和......
  • BZOJ 1461 题解
    考虑设计一个哈希函数\(hash(x)=f(x)\timesbase^x\)。其中\(f(x)\)表示\(\sum_{j=1}^{i-1}[j<i]\)。然后类似于滑动窗口计算区间哈希值,加入一个数就计算贡献,减去一个数就计算这个数产生了贡献,两个东西都可以树状数组维护,那么愉快做完了。#include<bits/stdc++.h>#de......