Educational Codeforces Round 134

發表於 更新於 分類於 ， Disqus： 文章字數： 1.5k 所需閱讀時間 ≈ 5 分鐘
F(二分图,hall's theorem)

CF tracker

Edu List

https://codeforces.com/contest/1721

F. Matching Reduction

给2分图, 左侧n1个点, 右侧n2个点, m条边

2种询问

第一种, 删除最少的点, 让最大匹配的值 正好少1, 输出具体选点方案, 剩余的匹配边的index和

第二种, (只会紧跟着第一种, 输出实际的匹配方案)

注意的是,在输出询问的结果前是无法读下一个的, 你需要fflush 输出后才能读下一个询问

范围

n1,n2 [1,2e5]

m 2e5

q 2e5

8s

512mb

强制在线

我的思路

极端一点, 不妨设每次都有1和2的询问, 就变成了如何维护二分图的匹配了

有点想到 abc215 的霍尔定理(左侧n点,右侧m点, 最大匹配为n的充分必要条件, 左侧的任意k个点集子集,连右侧点的个数都>=k)

所以如果 当前的匹配 刚好一侧点=匹配个数, 那么这一侧就随便删除一个点就行, 并且还满足这一侧的点=匹配数

问题来到 当匹配数 < 左侧点, 右侧点 时如何处理

1
2
3
4
1 -> 4
2 -> 4
3 -> 5
3 -> 6

比如这个就是两侧都是3个点,但是最大匹配只是2, 看上去, 删除3或者4都能让个数-1

再变化

1
2
3
4
5
6
1 -> 4
2 -> 4
3 -> 5
3 -> 6
7 -> 8
7 -> 9

不论删除3还是7 都可以让匹配数-1, 但是 都不会让匹配数 = 一侧点数

主要感觉霍尔定理还是和完美匹配挂钩

考虑直接匹配, 得到一个方案, 如果删除的点不在匹配中, 那么一定对个数无影响

所以至少需要删除一个匹配中的点

虽然匹配过程有顺序, 但是因为点是可以乱序, 所以考虑如果让最后一个失配 会怎么样

  1. 删除左侧点,

那么 左侧且在它前面的未匹配点不会影响,因为没匹配它时也未找到方案(在匈牙利算法中一个匹配成功的点会一直在匹配中)

左侧未匹配在它之后的可能会有影响, 设它是 u0 -> v0, 而后面的是u1 能通过某条路径(不一定直接,可能和前面的点走反边)和v0 匹配, 而u0 可以匹配某个当前右侧未匹配的 v, 那么这种情况 会有更大匹配, 而当前就是最大匹配矛盾,

所以如果有u1有路径和v0 匹配则 u0 一定没有额外可匹配的点,(这种情况删除v0即可, 空出来的u0不会被任何匹配)

否则所有u1都没有路径到v0, (这种情况删除u0即可,空出来的v0不会被任何匹配,其实左右交换是有对称性的)

综上得到, 每次只需要删除一个点(左右中一个和另一侧 未配点没有匹配关系的)

how 找

好处是上面的方案 所有匹配都没有变化, 只是减少, 而不会交换匹配的点

那么不如先跑一遍最大匹配, 然后枚举点和边, 计算每个点和未匹配的点有边的个数(O(E+V))

丢进set< pair<个数,点id>>维护

然后删除时更新一下set, 每条边更新一次, O(E log E)

然后随便set维护一下匹配方案

似乎就没了?

但是想了个反例

1
2
3
4
1-1
2-1
2-2
3-2

然后当前是1-1和2-2, 注意到右侧2没有未匹配点和它相连, 所以如果删除它匹配的左侧1, 并不能让个数下降

所以需要 找到的是一侧匹配的点 有, 一侧没有的这种去删除, 否则 所有的点都没有额外连接点了(就可以任意一个)

代码

https://codeforces.com/contest/1721/submission/189287144

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,n) for (int i=a;i<(int)n;i++)
#define per(i,a,n) for (int i=n;i-->(int)a;)
int read(){int r;scanf("%intd",&r);return r;} // read

int n;
vector<pair<int,int> > g[400010];
bool vis[400010];
array<int,2> u2ve[400010]; // 0表示未匹配, [u] = {v,edge idx}
bool del[400010];
int cnt[400010]; // 点和未匹配点的边的条数

bool dfs(int u){ // u左侧点
  vis[u]=true;
  for(auto [v,idx]:g[u]) if(!vis[v]){
    vis[v]=true;
    if(!u2ve[v][0] or dfs(u2ve[v][0])) {
      u2ve[v]={u,idx};
      return true;
    }
  }
  return false;
}

int main(){
  int n1 = read(); // 左
  int n2 = read(); // 右
  int m = read(); // 边
  int q = read(); // 询问
  rep(i,0,m){
    int x = read(); // 1-index
    int y = n1+read(); // (n1+1)-index
    g[x].push_back({y,i+1});
    g[y].push_back({x,i+1});
  }
  rep(l,1,n1+1) if(dfs(l)) fill(vis+1,vis+n1+n2+1,false);

  set<int> me;// 边id, match edge
  set<pair<int,int>, greater<pair<int,int>> > ci; // {count, point id}, 大根
  ll ans=0;
  rep(r,n1+1,n1+n2+1) if(u2ve[r][0]) {
    // printf("r=%d -> l=%d\n",r,u2ve[r][0]);
    auto [l,eid]=u2ve[r];
    ans+=eid;
    u2ve[l]={r,eid};//建立左侧到右侧的配对
    me.insert(eid);
  }
  rep(u,1,n1+n2+1) if(u2ve[u][0]){
    int c=0; // 有连接未配对的个数
    for(auto [v,eid]:g[u]) c+= !u2ve[v][0];
    ci.insert({cnt[u]=c,u});
    // printf("cnt[%d]=%d\n",u,cnt[u]);
  }

  auto update=[&](int u){ // u-v删除v后, 更新与u有关的
    for(auto [v,eid]:g[u]) {
      ci.erase({cnt[v],v});
      cnt[v]++;
      ci.insert({cnt[v],v});
    }
  };

  while(q--){
    int op = read();
    if(op == 1){
      while(true){
        auto [c,u]=*ci.begin();
        ci.erase(ci.begin());
        auto [v,eid]=u2ve[u];
        if(me.count(eid)){ // 还未被删
          printf("1\n");
          if(u<=n1) printf("%d\n",u); // 删除u
          else printf("-%d\n",u-n1);
          ans-=eid;
          printf("%lld\n",ans);
          me.erase(eid);
          // 更新u
          update(v);
          break;
        }
      }
    }else{ // == 2
      printf("%d\n",(int)me.size());
      for(auto eid:me) printf("%d ",eid);
      printf("\n");
    }
    fflush(stdout); // 强制在线
  }
  return 0;
}

题解

先找一个最大匹配

总结

当时比赛时间不够了, 思路还是有的

F

看来是属于 时间够就能过的题

参考

官方

hall’s theorem