头像

Protein

OIer


访客:12356

离线:9小时前


新鲜事 原文

Protein
6天前
吉林市第一中学20级01班-信息学竞赛负责人 get√


新鲜事 原文

Protein
21天前
我有十二省状元邵马安平学长的全部师资力量 我没有理由不成功


活动打卡代码 AcWing 969. 志愿者招募

Protein
21天前
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1010, M = 30010, INF = 1e9;
int n, m, S, T;
int h[N], ptr[M], val[M], f[M], w[M], idx;
int q[N], d[N], pre[N], incf[N];
bool st[N];
void add(int a, int b, int c, int d) {
    val[idx] = b, f[idx] = c, w[idx] = d, ptr[idx] = h[a], h[a] = idx++;
    val[idx] = a, f[idx] = 0, w[idx] = -d, ptr[idx] = h[b], h[b] = idx++;
}
bool SPFA() {
    int hh = 0, tt = 1;
    memset(d, 0x3f, sizeof d);
    memset(incf, 0, sizeof incf);
    incf[S] = INF, d[S] = 0, q[0] = S;
    while (hh != tt) {
        int t = q[hh++];
        if (hh == N) hh = 0;
        st[t] = false;
        for (int i = h[t]; i != -1; i = ptr[i]) {
            int ver = val[i];
            if (f[i] && d[ver] > d[t] + w[i]) {
                d[ver] = d[t] + w[i], pre[ver] = i;
                incf[ver] = min(f[i], incf[t]);
                if (!st[ver]) {
                    q[tt++] = ver;
                    if (tt == N) tt = 0;
                    st[ver] = true;
                }
            }
        }
    }
    return incf[T] > 0;
}
int EK() {
    int cost = 0;
    while (SPFA()) {
        int t = incf[T];
        cost += t * d[T];
        for (int i = T; i != S; i = val[pre[i] ^ 1])
            f[pre[i]] -= t, f[pre[i] ^ 1] += t;
    }
    return cost;
}
int main() {
    cin >> n >> m;
    S = 0, T = n + 2;
    memset(h, -1, sizeof h);
    int last = 0;
    for (int i = 1, cur; i <= n && cin >> cur; i++) {
        if (last > cur) add(S, i, last - cur, 0);
        else if (last < cur) add(i, T, cur - last, 0);
        add(i, i + 1, INF - cur, 0), last = cur;
    }
    add(S, n + 1, last, 0);
    for (int a, b, c; m-- && cin >> a >> b >> c; ) 
        add(b + 1, a, INF, c);
    cout << EK() << endl;
    return 0;
}


活动打卡代码 AcWing 2184. 餐巾计划问题

Protein
21天前
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1610, M = 10010, INF = 1e9;
int n, p, x, xp, y, yp, S, T;
int h[N], ptr[M], val[M], f[M], w[M], idx;
int d[N], q[N], pre[N], incf[N];
bool st[N];
void add(int a, int b, int c, int d) {
    val[idx] = b, f[idx] = c, w[idx] = d, ptr[idx] = h[a], h[a] = idx++;
    val[idx] = a, f[idx] = 0, w[idx] = -d, ptr[idx] = h[b], h[b] = idx++;
}
bool SPFA() {
    int hh = 0, tt = 1;
    memset(d, 0x3f, sizeof d);
    memset(incf, 0, sizeof incf);
    q[0] = S, d[S] = 0, incf[S] = INF;
    while (hh != tt) {
        int t = q[hh++];
        if (hh == N) hh = 0;
        st[t] = false;
        for (int i = h[t]; i != -1; i = ptr[i]) {
            int ver = val[i];
            if (f[i] && d[ver] > d[t] + w[i]) {
                d[ver] = d[t] + w[i];
                pre[ver] = i, incf[ver] = min(f[i], incf[t]);
                if (!st[ver]) {
                    q[tt++] = ver;
                    if (tt == N) tt = 0;
                    st[ver] = true;
                }
            }
        }
    }
    return incf[T] > 0;
}
int EK() {
    int cost = 0;
    while (SPFA()) {
        int t = incf[T];
        cost += t * d[T];
        for (int i = T; i != S; i = val[pre[i] ^ 1]) 
            f[pre[i]] -= t, f[pre[i] ^ 1] += t;
    }
    return cost;
}
int main() {
    cin >> n >> p >> x >> xp >> y >> yp;
    S = 0, T = n * 2 + 1;
    memset(h, -1, sizeof h);
    for (int i = 1, r; i <= n && cin >> r; i++) { 
        add(S, i, r, 0);
        add(n + i, T, r ,0);
        add(S, n + i, INF, p);
        if (i < n) add(i, i + 1, INF, 0);
        if (i + x <= n) add(i, n + i + x, INF, xp);
        if (i + y <= n) add(i, n + i + y, INF, yp);
    }
    cout << EK() << endl;
    return 0;
}



Protein
21天前
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 310, M = 2010, INF = 1e9;
int n, m, S, T;
int h[N], ptr[M], val[M], w[M], f[M], idx;
int q[N], d[N], pre[N], incf[N];
bool st[N];
void add(int a, int b, int c, int d) {
    val[idx] = b, f[idx] = c, w[idx] = d, ptr[idx] = h[a], h[a] = idx++;
    val[idx] = a, f[idx] = 0, w[idx] = -d, ptr[idx] = h[b], h[b] = idx++;
}
int get(int x, int y) {
    return (x * (m + 1) + y);
}
bool SPFA() {
    int hh = 0, tt = 1;
    memset(d, -0x3f, sizeof d);
    memset(incf, 0, sizeof incf);
    q[0] = S, incf[S] = INF, d[S] = 0;
    while (hh != tt) {
        int t = q[hh++];
        if (hh == N) hh = 0;
        st[t] = false;
        for (int i = h[t]; i != -1; i = ptr[i]) {
            int ver = val[i];
            if (f[i] && d[ver] < d[t] + w[i]) {
                d[ver] = d[t] + w[i];
                pre[ver] = i, incf[ver] = min(f[i], incf[t]);
                if (!st[ver]) {
                    q[tt++] = ver;
                    if (tt == N) tt = 0;
                    st[ver] = true;
                }
            }
        }
    }
    return incf[T] > 0;
}
int EK() {
    int cost = 0;
    while (SPFA()) {
        int t = incf[T];
        cost += t * d[T];
        for (int i = T; i != S; i = val[pre[i] ^ 1]) 
            f[pre[i]] -= t, f[pre[i] ^ 1] += t;
    }
    return cost;
}
int main() {
    int A, B;
    cin >> A >> B >> n >> m;
    S = (n + 1) * (m + 1), T = S + 1;
    memset(h, -1, sizeof h);
    for (int i = 0; i <= n; i++) 
        for (int j = 0, c; j < m && cin >> c; j++) {
            add(get(i, j), get(i, j + 1), 1, c);
            add(get(i, j), get(i, j + 1), INF, 0);
        }
    for (int i = 0; i <= m; i++)
        for (int j = 0, c; j < n && cin >> c; j++) {
            add(get(j, i), get(j + 1, i), 1, c);
            add(get(j, i), get(j + 1, i), INF, 0);
        }
    for (int k, x, y; A-- && cin >> k >> x >> y; ) 
        add(S, get(x, y), k, 0);
    for (int r, x, y; B-- && cin >> r >> x >> y; )
        add(get(x, y), T, r, 0);
    cout << EK() << endl;
    return 0;
}


活动打卡代码 AcWing 382. K取方格数

Protein
21天前
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 5010, M = 20010, INF = 1e9;
int n, k, S, T;
int h[N], ptr[M], val[M], f[M], w[M], idx;
int q[N], d[N], pre[N], incf[N];
bool st[N];
void add(int a, int b, int c, int d) {
    val[idx] = b, f[idx] = c, w[idx] = d, ptr[idx] = h[a], h[a] = idx++;
    val[idx] = a, f[idx] = 0, w[idx] = -d, ptr[idx] = h[b], h[b] = idx++;
}
int get(int x, int y, int t) {
    return (x * n + y) * 2 + t;
}
bool SPFA() {
    int hh = 0, tt = 1;
    memset(d, -0x3f, sizeof d);
    memset(incf, 0, sizeof incf);
    q[0] = S, d[S] = 0, incf[S] = INF;
    while (hh != tt) {
        int t = q[hh++];
        if (hh == N) hh = 0;
        st[t] = false;
        for (int i = h[t]; i != -1; i = ptr[i]) {
            int ver = val[i];
            if (f[i] && d[ver] < d[t] + w[i]) {
                d[ver] = d[t] + w[i];
                pre[ver] = i, incf[ver] = min(f[i], incf[t]);
                if (!st[ver]) {
                    q[tt++] = ver;
                    if (tt == N) tt = 0;
                    st[ver] = true;
                }
            }
        }
    }
    return incf[T] > 0;
}
int EK() {
    int cost = 0;
    while (SPFA()) {
        int t = incf[T];
        cost += t * d[T];
        for (int i = T; i != S; i = val[pre[i] ^ 1]) 
            f[pre[i]] -= t, f[pre[i] ^ 1] += t;
    }
    return cost;
}
int main() {
    cin >> n >> k;
    S = n * n * 2, T = n * n * 2 + 1;
    memset(h, -1, sizeof h);
    add(S, get(0, 0, 0), k, 0);
    add(get(n - 1, n - 1, 1), T, k, 0);
    for (int i = 0; i < n; i++) 
        for (int j = 0, c; j < n && cin >> c; j++) {
            add(get(i, j, 0), get(i, j, 1), 1, c);
            add(get(i, j, 0), get(i, j, 1), INF, 0);
            if (i + 1 < n) add(get(i, j, 1), get(i + 1, j, 0), INF, 0);
            if (j + 1 < n) add(get(i, j, 1), get(i, j + 1, 0), INF, 0);
        }
    cout << EK() << endl;
    return 0;
}


活动打卡代码 AcWing 2191. 数字梯形问题

Protein
21天前
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1200, M = 4000, INF = 1e8;
int n, m, S, T;
int h[N], ptr[M], val[M], f[M], w[M], idx;
int d[N], q[N], pre[N], incf[N];
int cost[30][30], id[30][30];
bool st[N];
void add(int a, int b, int c, int d) {
    val[idx] = b, f[idx] = c, w[idx] = d, ptr[idx] = h[a], h[a] = idx++;
    val[idx] = a, f[idx] = 0, w[idx] = -d, ptr[idx] = h[b], h[b] = idx++;
}
bool SPFA() {
    int hh = 0, tt = 1;
    memset(d, -0x3f, sizeof d);
    memset(incf, 0, sizeof incf);
    q[0] = S, d[S] = 0, incf[S] = INF;
    while (hh != tt) {
        int t = q[hh++];
        if (hh == N) hh = 0;
        st[t] = false;
        for (int i = h[t]; i != -1; i = ptr[i]) {
            int ver = val[i];
            if (f[i] && d[ver] < d[t] + w[i]) {
                d[ver] = d[t] + w[i];
                pre[ver] = i, incf[ver] = min(f[i], incf[t]);
                if (!st[ver]) {
                    q[tt++] = ver;
                    if (tt == N) tt = 0;
                    st[ver] = true;
                }
            }
        }
    }
    return incf[T] > 0;
}
int EK() {
    int cost = 0;
    while (SPFA()) {
        int t = incf[T];
        cost += t * d[T];
        for (int i = T; i != S; i = val[pre[i] ^ 1]) 
            f[pre[i]] -= t, f[pre[i] ^ 1] += t;
    }
    return cost;
}
int main() {
    cin >> m >> n;
    int cnt = 0;
    S = ++cnt, T = ++cnt;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m + i - 1; j ++ )
            cin >> cost[i][j], id[i][j] = ++cnt;
    memset(h, -1, sizeof h), idx = 0;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m + i - 1; j ++ ) {
            add(id[i][j] * 2, id[i][j] * 2 + 1, 1, cost[i][j]);
            if (i == 1) add(S, id[i][j] * 2, 1, 0);
            if (i == n) add(id[i][j] * 2 + 1, T, 1, 0);
            if (i < n) {
                add(id[i][j] * 2 + 1, id[i + 1][j] * 2, 1, 0);
                add(id[i][j] * 2 + 1, id[i + 1][j + 1] * 2, 1, 0);
            }
        }
    cout << EK() << endl;
    memset(h, -1, sizeof h), idx = 0;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m + i - 1; j ++ ) {
            add(id[i][j] * 2, id[i][j] * 2 + 1, INF, cost[i][j]);
            if (i == 1) add(S, id[i][j] * 2, 1, 0);
            if (i == n) add(id[i][j] * 2 + 1, T, INF, 0);
            if (i < n) {
                add(id[i][j] * 2 + 1, id[i + 1][j] * 2, 1, 0);
                add(id[i][j] * 2 + 1, id[i + 1][j + 1] * 2, 1, 0);
            }
        }
    cout << EK() << endl;
    memset(h, -1, sizeof h), idx = 0;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m + i - 1; j ++ ) {
            add(id[i][j] * 2, id[i][j] * 2 + 1, INF, cost[i][j]);
            if (i == 1) add(S, id[i][j] * 2, 1, 0);
            if (i == n) add(id[i][j] * 2 + 1, T, INF, 0);
            if (i < n) {
                add(id[i][j] * 2 + 1, id[i + 1][j] * 2, INF, 0);
                add(id[i][j] * 2 + 1, id[i + 1][j + 1] * 2, INF, 0);
            }
        }
    cout << EK() << endl;
    return 0;
}


活动打卡代码 AcWing 2193. 分配问题

Protein
21天前
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110, M = 6010, INF = 1e9;
int n, S, T;
int h[N], ptr[M], val[M], f[M], w[M], idx;
int q[N], d[N], incf[N], pre[N];
bool st[N];
void add(int a, int b, int c, int d) {
    val[idx] = b, f[idx] = c, w[idx] = d, ptr[idx] = h[a], h[a] = idx++;
    val[idx] = a, f[idx] = 0, w[idx] = -d, ptr[idx] = h[b], h[b] = idx++;
}
bool SPFA() {
    int hh = 0, tt = 1;
    memset(d, 0x3f, sizeof d);
    memset(incf, 0, sizeof incf);
    q[0] = S, d[S] = 0, incf[S] = INF;
    while (hh != tt) {
        int t = q[hh++];
        if (hh == N) hh = 0;
        st[t] = false;
        for (int i = h[t]; i != -1; i = ptr[i]) {
            int ver = val[i];
            if (f[i] && d[ver] > d[t] + w[i]) {
                d[ver] = d[t] + w[i];
                pre[ver] = i, incf[ver] = min(f[i], incf[t]);
                if (!st[ver]) {
                    q[tt++] = ver;
                    if (tt == N) tt = 0;
                    st[ver] = true;
                }
            }
        }
    }
    return incf[T] > 0;
}
int EK() {
    int cost = 0;
    while (SPFA()) {
        int t = incf[T];
        cost += t * d[T];
        for (int i = T; i != S; i = val[pre[i] ^ 1]) 
            f[pre[i]] -= t, f[pre[i] ^ 1] += t;
    }
    return cost;
}
int main() {
    cin >> n;
    memset(h, -1, sizeof h);
    S = 0, T = n * 2 + 1;
    for (int i = 1; i <= n; i++) 
        add(S, i, 1, 0), add(i + n, T, 1, 0);
    for (int i = 1; i <= n; i++)
        for (int j = 1, c; j <= n && cin >> c; j++) 
            add(i, n + j, 1, c);
    cout << EK() << endl;
    for (int i = 0; i < idx; i += 2)
        f[i] += f[i ^ 1], f[i ^ 1] = 0,
        w[i] = -w[i], w[i ^ 1] = -w[i ^ 1];
    cout << -EK() << endl;
    return 0;
}


活动打卡代码 AcWing 2194. 负载平衡问题

Protein
21天前
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 110, M = 1010, INF = 1e9;
int n, S, T, s[N];
int h[N], ptr[M], val[M], f[M], w[M], idx;
int d[N], q[N], pre[N], incf[N];
bool st[N];
void add(int a, int b, int c, int d) {
    val[idx] = b, w[idx] = d, f[idx] = c, ptr[idx] = h[a], h[a] = idx++;
    val[idx] = a, w[idx] = -d, f[idx] = 0, ptr[idx] = h[b], h[b] = idx++;
}
bool SPFA() {
    int hh = 0, tt = 1;
    memset(d, 0x3f, sizeof d);
    memset(incf, 0, sizeof incf);
    d[S] = 0, q[0] = S, incf[S] = INF;
    while (hh != tt) {
        int t = q[hh++];
        if (hh == N) hh = 0;
        st[t] = false;
        for (int i = h[t]; i != -1; i = ptr[i]) {
            int ver = val[i];
            if (f[i] && d[ver] > d[t] + w[i]) {
                d[ver] = d[t] + w[i];
                pre[ver] = i, incf[ver] = min(f[i], incf[t]);
                if (!st[ver]) {
                    q[tt++] = ver;
                    if (tt == N) tt = 0;
                    st[ver] = true;
                }
            }
        }
    }
    return incf[T] > 0;
}
int EK() {
    int cost = 0;
    while (SPFA()) {
        int t = incf[T];
        cost += t * d[T];
        for (int i = T; i != S; i = val[pre[i] ^ 1])
            f[pre[i]] -= t, f[pre[i] ^ 1] += t;
    }
    return cost;
}
int main() {
    cin >> n;
    S = 0, T = n + 1;
    int avg = 0;
    for (int i = 1; i <= n; i++) cin >> s[i], avg += s[i];
    memset(h, -1, sizeof h);
    for (int i = 1; i <= n; i++)
        add(i, i < n ? i + 1 : 1, INF, 1), 
        add(i, i > 1 ? i - 1 : n, INF, 1);
    avg /= n;
    for (int i = 1; i <= n; i++)
        if (avg < s[i]) add(S, i, s[i] - avg, 0);
        else if (avg > s[i]) add(i, T, avg - s[i], 0);
    cout << EK() << endl;
    return 0;
}


活动打卡代码 AcWing 2192. 运输问题

Protein
21天前
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 210, M = 120010, INF = 1e9;
int n, m, S, T;
int h[N], ptr[M], val[M], w[M], f[M], idx;
int q[N], pre[N], d[N], incf[N];
bool st[N];
void add(int a, int b, int c, int d) {
    val[idx] = b, f[idx] = c, w[idx] = d, ptr[idx] = h[a], h[a] = idx++;
    val[idx] = a, f[idx] = 0, w[idx] = -d, ptr[idx] = h[b], h[b] = idx++;
}
bool SPFA() {
    int hh = 0, tt = 1;
    memset(d, 0x3f, sizeof d);
    memset(incf, 0, sizeof incf);
    q[0] = S, d[S] = 0, incf[S] = INF;
    while (hh != tt) {
        int t = q[hh++];
        if (hh == N) hh = 0;
        st[t] = false;
        for (int i = h[t]; i != -1; i = ptr[i]) {
            int ver = val[i];
            if (f[i] && d[ver] > d[t] + w[i]) {
                d[ver] = d[t] + w[i];
                pre[ver] = i, incf[ver] = min(f[i], incf[t]);
                if (!st[ver]) {
                    q[tt++] = ver;
                    if (tt == N) tt = 0;
                    st[ver] = true;
                }
            }
        }
    }
    return incf[T] > 0;
}
int EK() {
    int cost = 0;
    while (SPFA()) {
        int t = incf[T];
        cost += t * d[T];
        for (int i = T; i != S; i = val[pre[i] ^ 1])
            f[pre[i]] -= t, f[pre[i] ^ 1] += t;
    }
    return cost;
}
int main() {
    cin >> n >> m;
    S = 0, T = n + m + 1;
    memset(h, -1, sizeof h);
    for (int i = 1, a; i <= n && cin >> a; i++) add(S, i, a, 0);
    for (int i = 1, a; i <= m && cin >> a; i++) add(n + i, T, a, 0);
    for (int i = 1; i <= n; i++)
        for (int j = 1, c; j <= m && cin >> c; j++) 
            add(i, n + j, INF, c);
    cout << EK() << endl;
    for (int i = 0; i < idx; i += 2) 
        f[i] += f[i ^ 1], f[i ^ 1] = 0,
        w[i] = -w[i], w[i ^ 1] = -w[i ^ 1];
    cout << -EK() << endl;
    return 0;
}