P3386 【模板】二分图最大匹配

dinic 是我们的好朋友。复杂度上界 O(m\sqrt(n))

#include <bits/stdc++.h>
#define d(x) cerr << #x << " => " << x << endl
#define dd(x) cerr << #x << endl
#define D cerr << "Passed [" << __FUNCTION__ << "] on line " << __LINE__ << endl
#define ms(x) memset(x, 0, sizeof x)
using namespace std;
int rd() {
    int f = 1, val = 0; char ch = getchar();
    while(!isdigit(ch)) f = (ch == '-' ? -1 : 1), ch = getchar();
    while(isdigit(ch)) val = val * 10 + ch - '0', ch = getchar();
    return f * val;
}

void file() {
    freopen("P3386_5.in", "r", stdin);
    //freopen("out.out", "w+", stdout);
}

const int N = 1010, M = 1e5 + 5;

struct Edge {
    int to, nxt, wei;
} Edge[M << 3];

int head[N], cur[N], dep[N], cnt = 1;

void addEdge(int u, int v, int w) {
    Edge[++cnt].to = v;
    Edge[cnt].wei = w;
    Edge[cnt].nxt = head[u];
    head[u] = cnt;
}

queue<int> Q;

int s, t, tot;

int bfs() {
    ms(dep);
    for(int i = 1; i <= tot; i++) cur[i] = head[i];
    while(!Q.empty()) Q.pop();
    Q.push(s); dep[s] = 1;
    while(!Q.empty()) {
        int u = Q.front(); Q.pop();
        for(int i = head[u]; i; i = Edge[i].nxt) {
            const int v = Edge[i].to;
            if(Edge[i].wei && !dep[v]) {
                dep[v] = dep[u] + 1;
                Q.push(v);
            }
        }
    }
    return dep[t];
}

int dfs(int u, int in) {
    if(u == t) return in;
    int out = 0;
    for(int i = cur[u]; i && in; i = Edge[i].nxt) {
        cur[u] = i;
        const int &v = Edge[i].to;
        if(Edge[i].wei && dep[v] == dep[u] + 1) {
            int res = dfs(v, min(in, Edge[i].wei));
            in -= res; out += res;
            Edge[i].wei -= res; Edge[i ^ 1].wei += res;
        }
    }

    if(out == 0) dep[u] = 0;
    return out;
}

signed main() {
#ifdef LOCAL
    file();
#endif
    int n = rd(), m = rd(), e = rd();
    s = 1, t = n + m + 2; tot = n + m + 2;
    for(int i = 1; i <= e; i++) {
        int u = rd() + 1, v = rd() + n + 1;
        addEdge(u, v, 1); addEdge(v, u, 0);
    }

    for(int i = 1; i <= n; i++) {   
        addEdge(1, i + 1, 1); addEdge(i + 1, 1, 0);
    }

    for(int i = 1; i <= m; i++) {
        addEdge(n + 1 + i, n + m + 2, 1); addEdge(n + m + 2, n + 1 + i, 0);
    }

    int ans = 0;
    while(bfs()) ans += dfs(s, 1e9);
    cout << ans << endl;
    return 0;
}

P4377 [USACO18OPEN]Talent Show G

分数规划。

分数规划一般来讲不会单独成题，一般来讲有以下几种形式：

0.不与任何算法结合，即分数规划裸题

1.与 0/10/10/1背包结合，即最优比率背包

2.与生成树结合，即最优比率生成树

3.与负环判定结合，即最优比率环

4.与网络流结合，即最大密度子图

5.与费用流结合，即最优比率流（这个是我乱叫的）

6.与其他的各种带选择的算法乱套，即最优比率啥啥的...

分数规划用来求一个分式的极值，基本思想是二分。

形式化地，给出 a[] 和 b[]，求一组 w \in \{0, 1\}，使得下式值最大（最小），且满足 w_i = 1 的个数不小于 k。

\frac{\sum_{i=1}^{n} a_i \times w_i}{\sum_{i=1}^{n} b_i \times w_i}

本题中二分后验证形式为 dp.

#include <bits/stdc++.h>
#define d(x) cerr << #x << " => " << x << endl
#define dd(x) cerr << #x << endl
#define D cerr << "Passed [" << __FUNCTION__ << "] on line " << __LINE__ << endl
#define ms(x) memset(x, 0, sizeof x)
#define int long long
using namespace std;
int rd() {
    int f = 1, val = 0; char ch = getchar();
    while(!isdigit(ch)) f = (ch == '-' ? -1 : 1), ch = getchar();
    while(isdigit(ch)) val = val * 10 + ch - '0', ch = getchar();
    return f * val;
}

void file() {
    freopen("in.in", "r", stdin);
    //freopen("out.out", "w+", stdout);
}

const int N = 1e4 + 4;

struct Cows {
    int w, t;
} cows[N << 1];

double myabs(double x) {
    return x < 0 ? -x : x;
}

const double eps = 1e-7;
int n, w;
double f[1010];

bool judge(double x) {
    std::fill(f + 1, f + 1010, -100000000);
    f[0] = 0;
    for(int j = 1; j <= n; j++) {
        for(int i = 1000; ~i; --i) {
            int jj = i + cows[j].w; jj = min(jj, 1000LL);
            if(jj <= 1000) {
                f[jj] = max(f[jj], f[i] + cows[j].t - x * cows[j].w);
            }
        }
    }
    for(int i = w; i <= 1000; i++) if(f[i] >= 0) return true;
    return false;
}

signed main() {
#ifdef LOCAL
    file();
#endif
    n = rd(), w = rd();
    for(int i = 1; i <= n; i++) {
        cows[i].w = rd(), cows[i].t = rd();
    }

    double l = 0, r = 998244353;
    while(myabs(r - l) > eps) {
        double mid = (l + r) / 2;
        if(judge(mid)) l = mid;
        else r = mid;
    }
    cout << (int)(1000LL * r) << endl;
    return 0;
}

P2257 YY的GCD

狄利克雷卷积。

瞎 jb 推导即可。

欧拉筛：每个数只会被它最小的因子筛去，适用于积性函数。

埃氏筛：每个数字都会被对应的因子筛出，适合每个因子都对函数值有贡献时使用。

要善于从和式意义上和改变枚举方法来化简式子。

#include <bits/stdc++.h>
#define d(x) cerr << #x << " => " << x << endl
#define dd(x) cerr << #x << endl
#define D cerr << "Passed [" << __FUNCTION__ << "] on line " << __LINE__ << endl
#define ms(x) memset(x, 0, sizeof x)
using namespace std;
int rd() {
    int f = 1, val = 0; char ch = getchar();
    while(!isdigit(ch)) f = (ch == '-' ? -1 : 1), ch = getchar();
    while(isdigit(ch)) val = val * 10 + ch - '0', ch = getchar();
    return f * val;
}

void file() {
    freopen("in.in", "r", stdin);
    //freopen("out.out", "w+", stdout);
}

const int N = 1e7 + 1000;
int isnt[N], prime[N], mu[N], g[N], pre_g[N], cnt;

void sieve(int n) {
    isnt[1] = isnt[0] = true;
    mu[1] = 1;
    for(int i = 2; i <= n; i++) {
        if(!isnt[i]) {
            prime[++cnt] = i;
            mu[i] = -1;
        }

        for(int j = 1; j <= cnt && i * prime[j] <= n; j++) {
            isnt[i * prime[j]] = true;
            if(i % prime[j] == 0) {
                mu[i * prime[j]] = 0;
                break;
            }
            mu[i * prime[j]] = mu[i] * mu[prime[j]];
        }
    }
}

void sieve2(int n) {
    ms(isnt);
    isnt[0] = isnt[1] = true;
    for(int i = 2; i <= n; i++) {
        if(!isnt[i]) {
            g[i] = 1;
            for(int j = 2; i * j <= n; j++) {
                g[i * j] += mu[j];
                isnt[i * j] = true;
            }
        }
    }
}

signed main() {
#ifdef LOCAL
    file();
#endif
    sieve(1e7 + 6);
    sieve2(1e7 + 6);
    for(int i = 1; i < N; i++) {
        pre_g[i] = pre_g[i - 1] + g[i];
    }

/*  
    for(int i = 1; i <= 100; i++) {
        cout << g[i] << " ";
    }
    cout << endl;
*/  

    int T = rd();
    while(T--) {
        int m = rd(), n = rd();
        long long ans = 0;
        for(int L = 1; L <= min(m, n); L++) {
            int R = min(min(m / (m / L), n / (n / L)), min(m, n));
            ans +=  1LL * (m / L) * (n / L) * (pre_g[R] - pre_g[L - 1]);
            L = R;
        }
        printf("%lld\n", ans);
    }

    return 0;
}

P1437 [HNOI2004]敲砖块

DP. 直接从上到下货从下到上 DP 没办法转移。

仔细观察性质后发现，一个点能否选择会依赖于右上的点的选择情况。因此可以从右向左dp。

#include <bits/stdc++.h>
#define d(x) cerr << #x << " => " << x << endl
#define dd(x) cerr << #x << endl
#define D cerr << "Passed [" << __FUNCTION__ << "] on line " << __LINE__ << endl
#define ms(x) memset(x, 0, sizeof x)
using namespace std;
int rd() {
    int f = 1, val = 0; char ch = getchar();
    while(!isdigit(ch)) f = (ch == '-' ? -1 : 1), ch = getchar();
    while(isdigit(ch)) val = val * 10 + ch - '0', ch = getchar();
    return f * val;
}

void file() {
    freopen("in.in", "r", stdin);
    //freopen("out.out", "w+", stdout);
}

const int N = 55;
int a[N][N], sum[N][N], dp[N][N][N * N];

signed main() {
#ifdef LOCAL
    file();
#endif
    int n = rd(), m = rd();
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n - i + 1; j++) {
            a[j][i] = rd();
        }
    }

    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n - i + 1; j++) {
            sum[i][j] = sum[i][j - 1] + a[i][j];
        }
    }

    memset(dp, -1, sizeof dp);
    int ans = 0;
//  for(int i = 1; i <= n; i++) dp[i][1][1] = a[i][1], ans = max(ans, a[i][1]);
    dp[n + 1][0][0] = 0;
    for(int i = n; i; i--) {
        for(int j = 0; j <= n - i + 1; j++) {
            for(int k = j * (1 + j) / 2; k <= m; ++k) {
                for(int l = max(0, j - 1); l <= n - i; l++) {
                    if(k - j >= 0 && dp[i + 1][l][k - j] != -1) {
                        dp[i][j][k] = max(dp[i][j][k], dp[i + 1][l][k - j] + sum[i][j]);
                        //cout << i << " " << j << " " << k << " " << i + 1 << " " << l << " " << k - j << " " << dp[i][j][k] << endl;
                    }
                }
                if(k <= m) ans = max(ans, dp[i][j][k]);
            }
        }
    }
    cout << ans << endl;

    return 0;
}

P3594 [POI2015]WIL-Wilcze doły

双指针套单调队列。

#include <bits/stdc++.h>
#define d(x) cerr << #x << " => " << x << endl
#define dd(x) cerr << #x << endl
#define D cerr << "Passed [" << __FUNCTION__ << "] on line " << __LINE__ << endl
#define ms(x) memset(x, 0, sizeof x)
#define int long long
using namespace std;
int rd() {
    int f = 1, val = 0; char ch = getchar();
    while(!isdigit(ch)) f = (ch == '-' ? -1 : 1), ch = getchar();
    while(isdigit(ch)) val = val * 10 + ch - '0', ch = getchar();
    return f * val;
}

void file() {
    freopen("in.in", "r", stdin);
    //freopen("out.out", "w+", stdout);
}

const int N = 4e6 + 5;
int a[N], sum[N], dif[N];
deque<int> Q;

signed main() {
#ifdef LOCAL
    file();
#endif
    int n = rd(), p = rd(), d = rd();
    for(int i = 1; i <= n; i++) {
        a[i] = rd(); 
        sum[i] = sum[i - 1] + a[i];
    }

    for(int i = 1; i <= n; i++) {
        if(i - d < 0) dif[i] = sum[i];
        else dif[i] = sum[i] - sum[i - d];
    }

    int l = 0, sum = 0, ans = d;
    for(int i = 1; i <= n; i++) {
        sum += a[i];
        while(!Q.empty() && dif[i] >= dif[Q.back()]) Q.pop_back();
        Q.push_back(i);
        while(sum - dif[Q.front()] > p) {
            sum -= a[++l];
            while(!Q.empty() && Q.front() - d + 1 <= l) Q.pop_front();
        }
        ans = max(i - l, ans);
    }

    cout << ans << endl;
    return 0;
}
最后修改：2021 年 02 月 11 日
© 允许规范转载
如果觉得我的文章对你有用，请随意赞赏