题目链接：https://qoj.ac/contest/1221/problem/6402

题目大意：求 $mex$ 最大的生成树。

做法

一个显然的事情，这道题目是拟阵交，第一个拟阵无环，第二个拟阵要求每条数字的边至多一条。

这个时候可以二分+拟阵交，也可以从小到达考虑 $\le c$ 的边的拟阵交，因为拟阵交的算法保证了，只要给一个交集中的元素（一般默认空集），就一定可以增广出最大的元素。

接下来默认用从小到大考虑的方法，因为少个 $log$ 。

以下时间复杂度默认点数与边数同阶。

暴力建图的话是 $O(n^3)$ ，虽然能过，但是能不能更加优秀？

这个时候有几个优化方向：

  1. bitset ，在翻代码的时候看到的，虽然没看具体怎么优化的，反正是有人这么干的。
  2. 等到遍历到在加入边，显然，我们没必要一开始就把图建出来，而是跑到一个点再把这个点的所有出边找到，发现由于是 BFS，所以每个点至多走一次，所以这个优化只快不慢，同时注意到图拟阵那边的出边是难的，可以采用并查集优化的方式，在 $O(n^2\alpha(n))$ 的时间解决这个特殊的拟阵交问题。
  3. 题解说可以 $O(n^2\sqrt{n})$ ，没懂具体咋搞的，但肯定不是一开始就把图建出来。后面经过询问，似乎是说最短路的总长度有个 bound ，又说和 Hopcroft Karp 的分析类似，但 Hopcroft Karp 我没有学过，这个方法先咕了，等以后再说吧。

但我写的是最暴力的三方做法，还要乘并查集的 $\alpha(n)$ 。

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
93
94
95
96
97
98
99
100
101
102
103
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+5;
const int M=2e6+5;
int n,m;
struct Edge{
    int x,y,c;
}e[N];int pf[N];
bool cmp(Edge x,Edge y){return x.c<y.c;}
bool in[N],col[N];

int fa[N];
int findfa(int x){return fa[x]==x?x:fa[x]=findfa(fa[x]);}
void mer(int x,int y){
    x=findfa(x);y=findfa(y);
    if(x!=y)fa[x]=y;
}
bool pd(int x,int y){return findfa(x)==findfa(y);}
void uinit(){
    for(int i=1;i<=n;i++)fa[i]=i;
}
struct node{
    int y,next;
}a[M];int len,las[N];
void ins(int x,int y){a[++len]={y,las[x]};las[x]=len;}
int typ[N];
void build(int lim){
    len=0;
    memset(las+1,0,sizeof(int)*lim);
    memset(typ+1,0,sizeof(int)*lim);
    for(int i=1;i<=lim;i++){
        if(!in[i])continue;
        uinit();
        for(int j=1;j<=lim;j++){
            if(i!=j && in[j])mer(e[j].x,e[j].y);
        }
        for(int j=1;j<=lim;j++){
            if(in[j])continue;
            if(!pd(e[j].x,e[j].y))ins(i,j);
            if(e[i].c==e[j].c || !col[e[j].c])ins(j,i);
        }
    }
    uinit();
    for(int i=1;i<=lim;i++){
        if(in[i])mer(e[i].x,e[i].y);
    }
    for(int i=1;i<=lim;i++){
        if(in[i])continue;
        if(!pd(e[i].x,e[i].y))typ[i]|=1;
        if(!col[e[i].c])typ[i]|=2;
    }
}

queue<int> q;
int pre[N];
bool solve(int lim){
    for(int i=1;i<=lim;i++)pre[i]=-1;
    for(int i=1;i<=lim;i++){
        if(typ[i]&1){
            pre[i]=0;
            q.push(i);
        }
    }
    while(!q.empty()){
        int x=q.front();q.pop();
        if(typ[x]&2){
            while(!q.empty())q.pop();
            while(x){
                col[e[x].c]^=1;
                in[x]^=1;
                x=pre[x];
            }
            return 1;
        }
        for(int k=las[x];k;k=a[k].next){
            int y=a[k].y;
            if(pre[y]==-1){
                pre[y]=x;
                q.push(y);
            }
        }
    }
    return 0;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].c);
    }
    sort(e+1,e+m+1,[](Edge x,Edge y){
        return x.c<y.c;
    });
    for(int i=1;i<=m;i++)pf[e[i].c]=i;
    for(int i=1;i<=n;i++)pf[i]=max(pf[i],pf[i-1]);
    for(int i=0;i<=n;i++){
        build(pf[i]);
        if(!solve(pf[i])){
            printf("%d\n",i);
            break;
        }
    }
    return 0;
}
坑

根号做法是啥。