$ 第四板块 $ $ 模板 $

目录

1.二分图最大匹配(匈牙利算法)

# include <bits/stdc++.h>
# define sc scanf
# define pr printf
using namespace std;

const int N = 510, M = 5e4 + 10;

int n, m, t, ans, idx;
int lk[N], e[M], ne[M], h[N];
bool vis[N];

void add(int u, int v){
    e[idx] = v, ne[idx] = h[u], h[u] = idx ++;
}

bool dfs(int u){
    for(int i = h[u]; ~i; i = ne[i]){
        int v = e[i];
        if(vis[v]) continue;
        vis[v] = true;
        if(!lk[v] || dfs(lk[v])){
            lk[v] = u;
            return true;
        }
    }

    return false;
}

int main(){
    idx = 1;
    sc("%d %d %d", &n, &m, &t);
    memset(h, -1, sizeof h);

    for(int i = 1, a, b; i <= t; i ++){
        sc("%d %d", &a, &b);
        add(a, b);
    }

    for(int i = 1; i <= n; i ++){
        for(int j = 1; j <= m; j ++) vis[j] = false;
        if(dfs(i)) ans ++;
    }

    pr("%d", ans);

    return 0;
}

2.KMP

LINK->SDOI
LINK->AcWing

# include <bits/stdc++.h>
# define sc scanf
# define pr printf
# define fir first
# define sec second
using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 1e6 + 10;

char a[N], b[N];
int n, m, cnt;
int fail[N];

int main(){
    cin >> a + 1 >> b + 1;

    n = strlen(a + 1), m = strlen(b + 1);

    for(int i = 1, t; i <= m; i ++){
        for(t = fail[i]; t && b[t + 1] != b[i + 1]; t = fail[t]);
        fail[i + 1] = b[i + 1] == b[t + 1] ? t + 1 : 0;
    }

    cnt = 0;
    for(int i = 1, t = 0; i <= n; i ++){
        for(; t && a[i] != b[t + 1]; t = fail[t]);
        if(a[i] == b[t + 1]) t ++;
        if(t == m) cnt ++;
    }

    pr("%d", cnt);

    return 0;
}

3.最大公约数和最小公倍数

证明

# include <bits/stdc++.h>
# define sc scanf
# define pr printf
using namespace std;

typedef long long LL;

inline LL gcd(LL x, LL y){
    return y ? gcd(y, x % y) : x;
}

int main(){
    LL a, b;

    sc("%lld %lld", &a, &b); 

    LL g = gcd(a, b);

    pr("最大公约数:%lld\n最小公倍数:%lld", g, g * (a / g) * (b / g));

    return 0;
}