欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-06-02 23:47:41
题意 题目链接 $n$个人,每个人可以在第$a_i$天或第$b_i$,一天最多考一场试,问在最优的情况下,最晚什么时候结束 Sol 自己只能想到暴力匈牙利二分图匹配,然而还是被构造数据卡了。。 标算很神奇。 同样考虑把题目中给出的模型建成二分图,左侧代表每个人,右侧代表每一天的考试 然后我们把右侧每 ......

题意

题目链接

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

sol

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

标算很神奇。

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

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

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

分情况讨论一下:

考虑当前的联通块:

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

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

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

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

cf1027F. Session in BSU(并查集 匈牙利)
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<vector>
#define ll long long 
using namespace std;
const int maxn = 1e6 + 10, inf = 1e9 + 7;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int n;
int a[maxn], b[maxn], date[maxn << 1], cnt, vis[maxn], link[maxn], atk[maxn];
vector<int> v[maxn];
int aug(int x, int tim) {
    for(int i = 0; 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 1;
            }
    }
    return 0;
}
main() {
    n = read();
    for(int i = 1; i <= n; i++) a[i] = read(), b[i] = read(), date[++cnt] = a[i], date[++cnt] = b[i];
    sort(date + 1, date + cnt + 1);
    cnt = unique(date + 1, date + cnt + 1) - date - 1;
    for(int i = 1; i <= n; i++) {
        a[i] = lower_bound(date + 1, date + cnt + 1, a[i]) - date, 
        b[i] = lower_bound(date + 1, date + cnt + 1, b[i]) - date;        
        v[a[i]].push_back(i);
        v[b[i]].push_back(i);
    }
    int ans = 0, tot = 0;
    for(int i = 1; i <= cnt; i++) {
        if(aug(i, i)) 
            tot++;
        if(tot == n) {
            printf("%d", date[i]); return 0;
        }        
    }
    puts("-1");
    return 0;
}
/*
3
23 27
22 26
27 30
*/
暴力匈牙利tle on test 56

 

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 2 * 1e6 + 10;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int n, a[maxn], b[maxn], date[maxn << 1], cnt = 0, 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 = 1; i <= n; i++) a[i] = read(), b[i] = read(), date[++cnt] = a[i], date[++cnt] = b[i];
    sort(date + 1, date + cnt + 1);
    cnt = unique(date + 1, date + cnt + 1) - date - 1;
    for(int i = 1; i <= n; i++)
        a[i] = lower_bound(date + 1, date + cnt + 1, a[i]) - date,
        b[i] = lower_bound(date + 1, date + cnt + 1, b[i]) - date;
    for(int i = 1; i <= cnt; i++) fa[i] = i, mx[i] = i;
    
    for(int i = 1; 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] = 1;
        else {puts("-1"); return 0;}
    }
    int ans = 0;
    for(int i = 1; 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 0;
}