cf1027F. Session in BSU(并查集 匈牙利)

题意

题目链接

$n$个人，每个人可以在第$a_i$天或第$b_i$，一天最多考一场试，问在最优的情况下，最晚什么时候结束

Sol

自己只能想到暴力匈牙利二分图匹配，然而还是被构造数据卡了。。

标算很神奇。

同样考虑把题目中给出的模型建成二分图，左侧代表每个人，右侧代表每一天的考试

然后我们把右侧每个人能选择的两个点之间连边

这样模型就由二分图转化成了一条链上的问题。

分情况讨论一下：

考虑当前的联通块：

1、边数大于点数：因为每个条边都必须与一个点匹配，因此这样肯定无解

2、边数 = 点数：很显然是一棵基环树，输出最大值即可

3、边数 < 点数：这是一棵树，输出次大值即可

这样我们用并查集维护一下最大值，次大值。就做完了。。

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<cstring>

#include<vector>

#define LL long long

using namespace std;

const int MAXN = 1e6 + , INF = 1e9 + ;

inline int read() {

    char c = getchar(); int x = , f = ;

    while(c < '' || c > '') {if(c == '-') f = -; c = getchar();}

    while(c >= '' && c <= '') x = x *  + c - '', c = getchar();

    return x * f;

}

int N;

int a[MAXN], b[MAXN], date[MAXN << ], cnt, vis[MAXN], link[MAXN], atk[MAXN];

vector<int> v[MAXN];

int Aug(int x, int tim) {

    for(int i = ; i < v[x].size(); i++) {

        int to = v[x][i];

        if(vis[to] == tim) continue;

        vis[to] = tim;

        if(!link[to] || Aug(link[to], tim))

            {

                link[to] = x;

                return ;

            }

    }

    return ;

}

main() {

    N = read();

    for(int i = ; i <= N; i++) a[i] = read(), b[i] = read(), date[++cnt] = a[i], date[++cnt] = b[i];

    sort(date + , date + cnt + );

    cnt = unique(date + , date + cnt + ) - date - ;

    for(int i = ; i <= N; i++) {

        a[i] = lower_bound(date + , date + cnt + , a[i]) - date,

        b[i] = lower_bound(date + , date + cnt + , b[i]) - date;

        v[a[i]].push_back(i);

        v[b[i]].push_back(i);

    }

    int ans = , tot = ;

    for(int i = ; i <= cnt; i++) {

        if(Aug(i, i))

            tot++;

        if(tot == N) {

            printf("%d", date[i]); return ;

        }

    }

    puts("-1");

    return ;

}

/*

3

23 27

22 26

27 30

*/

暴力匈牙利TLE ON TEST 56

#include<cstdio>

#include<algorithm>

using namespace std;

const int MAXN =  * 1e6 + ;

inline int read() {

    char c = getchar(); int x = , f = ;

    while(c < '' || c > '') {if(c == '-') f = -; c = getchar();}

    while(c >= '' && c <= '') x = x *  + c - '', c = getchar();

    return x * f;

}

int N, a[MAXN], b[MAXN], date[MAXN << ], cnt = , fa[MAXN], tag[MAXN], mx[MAXN], smx[MAXN];

int find(int x) {

    if(fa[x] == x) return fa[x];

    else return fa[x] = find(fa[x]);

}

int main() {

    N = read();

    for(int i = ; i <= N; i++) a[i] = read(), b[i] = read(), date[++cnt] = a[i], date[++cnt] = b[i];

    sort(date + , date + cnt + );

    cnt = unique(date + , date + cnt + ) - date - ;

    for(int i = ; i <= N; i++)

        a[i] = lower_bound(date + , date + cnt + , a[i]) - date,

        b[i] = lower_bound(date + , date + cnt + , b[i]) - date;

    for(int i = ; i <= cnt; i++) fa[i] = i, mx[i] = i;

    for(int i = ; i <= N; i++) {

        int x = a[i], y = b[i];

        int fx = find(x), fy = find(y);

        if(find(x) != find(y)) {

            fa[fy] = fx;  tag[fx] |= tag[fy];

            if(mx[fy] > mx[fx]) smx[fx] = max(smx[fx], max(smx[fy], mx[fx])), mx[fx] = mx[fy];

            else smx[fx] = max(smx[fx], mx[fy]);

        }

        else if(!tag[fx]) tag[fx] = ;

        else {puts("-1"); return ;}

    }

    int ans = ;

    for(int i = ; i <= cnt; i++) {

        if(fa[i] == i)

            if(tag[i]) ans = max(ans, mx[i]);

            else ans = max(ans, smx[i]);

    }

    printf("%d\n", date[ans]);

    return ;

}