【总结】2019.6~2019.7模拟赛

没有时间把每次模拟赛的每道题都拿来总结,放一些对我来说收获比较大的吧。

LGOJ-P2860

传送门

解题思路

题目要求添加最少的边,让所有的点都在环上。考虑把图按照边双缩成树,然后把所有叶子往根上连

代码

// luogu-judger-enable-o2
// luogu-judger-enable-o2
#include <iostream>
#include <cstring>
#include <stack>
#include <vector>

using namespace std;

const int MAXN = 5e3 + 5;
const int MAXM = 1e4 + 5;

int n, m;
int head[MAXM << 1], to[MAXM << 1], nxt[MAXM << 1], cnt = -1;
int low[MAXN], dfn[MAXN], deg[MAXN], col[MAXN], tot, tc;
int ans;
bool vis[MAXM << 1];
stack<int> stk;

void AddEdge(int u, int v) {
    cnt++; to[cnt] = v; nxt[cnt] = head[u]; head[u] = cnt;
    cnt++; to[cnt] = u; nxt[cnt] = head[v]; head[v] = cnt;
}

void Tarjan(int u) {
    low[u] = dfn[u] = ++tc; stk.push(u);
    for (int i = head[u]; ~i; i = nxt[i]) {
        vis[i] = true;
        if (!vis[i ^ 1]) {
            int v = to[i];
            if (!dfn[v]) {
                Tarjan(v);
                low[u] = min(low[u], low[v]);
            } else {
                low[u] = min(low[u], dfn[v]);
            }
        }
    }
    if (low[u] == dfn[u]) {
        col[u] = ++tot;
        while (!stk.empty()) {
            int v = stk.top(); stk.pop();
            col[v] = tot;
            if (v == u) break;
        }
    }
}

int main() {
    cin >> n >> m;
    int u, v;
    memset(head, -1, sizeof(head));
    for (int i = 1; i <= m; i++) {
        cin >> u >> v;
        AddEdge(u, v);
    }
    Tarjan(1);
    for (int i = 1; i <= n; i++) {
        for (int j = head[i]; ~j; j = nxt[j]) {
            vis[j] = false;
            if (vis[j ^ 1]) {
                v = to[j];
                if (col[i] != col[v]) {
                    deg[col[i]]++;
                    deg[col[v]]++;
                }
            }
        }
    }
    for (int i = 1; i <= tot; i++) {
        if (deg[i] == 1) ans++;
    }
    cout << (ans + 1 >> 1) << endl;
    return 0;
}

LGOJ-P2656

传送门

解题思路

在环上的边可以跑满,不在环上的边只能跑一次。考虑缩点,把能跑满的边加到颜色的点权上,跑一次的边建出来,然后SPFA带着点权跑最长路

代码

// luogu-judger-enable-o2
#include <iostream>
#include <cstring>
#include <stack>
#include <queue>
#include <cmath>

using namespace std;

const int MAXN = 8e4 + 5;
const int MAXM = 2e5 + 5;

struct Edge{
    int to, val;
    Edge *nxt;

    Edge(int to, int val, Edge *nxt) : to(to), val(val), nxt(nxt) {}
};

Edge *hd1[MAXN], *hd2[MAXN];

void Add1(int u, int v, int w) {
    hd1[u] = new Edge(v, w, hd1[u]);
}

void Add2(int u, int v, int w) {
    hd2[u] = new Edge(v, w, hd2[u]);
}

int n, m;
int inx[MAXM], iny[MAXM], inz[MAXM];
double inr[MAXM];
int low[MAXN], col[MAXN], dfn[MAXN], tc, tot;
stack<int> stk;
int w[MAXN << 1], dis[MAXN << 1];
bool vis[MAXN << 1];

void Tarjan(int u) {
    stk.push(u); dfn[u] = low[u] = ++tc;
    for (Edge *e = hd1[u]; e; e = e->nxt) {
        int v = e->to;
        if (!dfn[v]) {
            Tarjan(v);
            low[u] = min(low[u], low[v]);
        } else {
            if (!col[v]) low[u] = min(low[u], dfn[v]);
        }
    }
    if (low[u] == dfn[u]) {
        col[u] = ++tot;
        while (!stk.empty()) {
            int v = stk.top(); stk.pop();
            col[v] = tot;
            if (v == u) break;
        }
    }
}

int GetTotal(int x, double y) {
    int ret = 0;
    while (x) {
        ret += x;
        x = (int)floor((double)x * y);
    }
    return ret;
}

int Id(int u, int typ) {
    if (typ == 0) return col[u];
    else return col[u] + tot;
}

void Rebuild() {
    for (int i = 1; i <= m; i++) {
        if (col[inx[i]] == col[iny[i]]) w[col[inx[i]]] += GetTotal(inz[i], inr[i]);
        else Add2(Id(inx[i], 1), Id(iny[i], 0), inz[i]);
    }
    for (int i = 1; i <= tot; i++) Add2(i, i + tot, w[i]);
}

void Spfa(int s) {
    memset(dis, 0x8f, sizeof(dis));
    queue<int> q; q.push(s); dis[s] = 0; vis[s] = true;
    while (!q.empty()) {
        int u = q.front(); q.pop(); vis[u] = false;
        for (Edge *e = hd2[u]; e; e = e->nxt) {
            int v = e->to;
            if (dis[v] < dis[u] + e->val) {
                dis[v] = dis[u] + e->val;
                if (!vis[v]) {
                    vis[v] = true;
                    q.push(v);
                }
            }
        }
    }
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> inx[i] >> iny[i] >> inz[i] >> inr[i];
        Add1(inx[i], iny[i], inz[i]);
    }
    for (int i = 1; i <= n; i++) {
        if (!dfn[i]) Tarjan(i);
    }
    for (int i = 1; i <= n; i++) {
        cerr << col[i] << ' ';
    }
    cerr << endl;
    Rebuild();
    int s;
    cin >> s;
    Spfa(Id(s, 0));
    int ans = 0;
    for (int i = 1; i <= tot * 2; i++) ans = max(ans, dis[i]);
    cout << ans << endl;
    return 0;
}

LGOJ-P5030

传送门

解题思路

考虑到棋子走目字而不是日字,可以按照行来染色,而不是点

代码

// luogu-judger-enable-o2
#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

const int MAXN = 205;
const int INF = 0x3f3f3f3f;
const int X[] = {-1, -1, -3, -3, 1, 1, 3, 3, 0};
const int Y[] = {-3, 3, -1, 1, -3, 3, -1, 1, 0};

int n, m, k;
int g[MAXN][MAXN];

struct Edge{
    int to, val;
    Edge *nxt, *ops;
    Edge(int to, int val, Edge *nxt) : to(to), val(val), nxt(nxt) {}
};

Edge *head[MAXN * MAXN];

void AddEdge(int u, int v, int w) {
    head[u] = new Edge(v, w, head[u]);
    head[v] = new Edge(u, 0, head[v]);
    head[u]->ops = head[v]; head[v]->ops = head[u];
}

namespace MaxFlow{
    int dep[MAXN * MAXN], gap[MAXN * MAXN], s, t, res, tot;
    Edge *cur[MAXN * MAXN];

    void Bfs() {
        memset(dep, -1, sizeof(dep));
        memset(gap, 0, sizeof(gap));
        queue<int> q; q.push(t); dep[t] = 0; gap[dep[t]]++;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (Edge *e = head[u]; e; e = e->nxt) {
                int v = e->to;
                if (dep[v] != -1) continue;
                dep[v] = dep[u] + 1;
                gap[dep[v]]++;
                q.push(v);
            }
        }
    }

    int Dfs(int u, int flow) {
        if (u == t) {
            res += flow;
            return flow;
        }
        int used = 0;
        for (Edge *&e = cur[u]; e; e = e->nxt) {
            int v = e->to;
            if (dep[v] == dep[u] - 1 && e->val) {
                int mi = Dfs(v, min(e->val, flow - used));
                if (mi) {
                    used += mi;
                    e->val -= mi;
                    e->ops->val += mi;
                }
                if (used == flow) return used;
            }
        }
        cur[u] = head[u];
        gap[dep[u]]--;
        if (gap[dep[u]] == 0) dep[s] = tot + 1;
        dep[u]++;
        gap[dep[u]]++;
        return used;
    }

    void Isap() {
        res = 0;
        memcpy(cur, head, sizeof(head));
        Bfs();
        while (dep[s] <= tot) Dfs(s, INF);
    }
}

int ID(int x, int y) {
    return (x - 1) * m + y;
}

int main() {
    cin >> n >> m >> k;
    int &s = MaxFlow :: s = 0;
    int &t = MaxFlow :: t = n * m + 1;
    MaxFlow :: tot = n * m + 2;
    for (int i = 1; i <= k; i++) {
        int x, y;
        cin >> x >> y;
        g[x][y] = 1;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (i % 2 == 1) AddEdge(s, ID(i, j), 1);
            else AddEdge(ID(i, j), t, 1);
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (g[i][j]) continue;
            if (i % 2 == 1) {
                for (int k = 0; k < 8; k++) {
                    int nx = i + X[k], ny = j + Y[k];
                    if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && !g[nx][ny]) AddEdge(ID(i, j), ID(nx, ny), 1);
                }
            }
        }
    }
    MaxFlow :: Isap();
    cout << n * m - k - MaxFlow :: res << endl;
    return 0;
}

LGOJ-P2469

传送门

解题思路

考虑费用流。模型是带权最小路径覆盖。

代码

// luogu-judger-enable-o2
#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

const int MAXN = 805;
const int MAXM = 1.5e4 + 5;
const int INF = 0x3f3f3f3f;

int n, m, a[MAXN];

struct Edge{
    int to, val, cost;
    Edge *nxt, *ops;

    Edge() {}

    Edge(int to, int val, int cost, Edge *nxt) : to(to), val(val), cost(cost), nxt(nxt) {}
};

Edge *head[MAXN << 1];

void AddEdge(int u, int v, int w, int c) {
    head[u] = new Edge(v, w, c, head[u]);
    head[v] = new Edge(u, 0, -c, head[v]);
    head[u]->ops = head[v]; head[v]->ops = head[u];
}

namespace ZKW{
    Edge *cur[MAXN << 1];
    int vis[MAXN << 1], dis[MAXN << 1], s, t, res, ans;

    int Spfa() {
        memset(dis, INF, sizeof(dis));
        memset(vis, 0, sizeof(vis));
        queue<int> q; q.push(s); dis[s] = 0; vis[s] = 1;
        while (!q.empty()) {
            int u = q.front(); q.pop(); vis[u] = 0;
            for (Edge *e = head[u]; e; e = e->nxt) {
                int v = e->to;
                if (dis[v] > dis[u] + e->cost && e->val) {
                    dis[v] = dis[u] + e->cost;
                    if (!vis[v]) {
                        vis[v] = 1;
                        q.push(v);
                    }
                }
            }
        }
        return dis[t] < INF;
    }

    int Dfs(int u, int flow) {
        if (u == t) {
            vis[u] = 1;
            res += flow;
            return flow;
        }
        int used = 0;
        vis[u] = 1;
        for (Edge *&e = cur[u]; e; e = e->nxt) {
            int v = e->to;
            if ((!vis[v] || v == t) && e->val && dis[u] + e->cost == dis[v]) {
                int mi = Dfs(v, min(e->val, flow - used));
                if (mi) {
                    e->val -= mi;
                    e->ops->val += mi;
                    ans += e->cost * mi;
                    used += mi;
                }
                if (used == flow) break;
            }
        }
        vis[u] = 0;
        return used;
    }

    void Work() {
        res = 0; ans = 0;
        while (Spfa()) {
            while (true) {
                memset(vis, 0, sizeof(vis));
                memcpy(cur, head, sizeof(cur));
                Dfs(s, INF);
                if (!vis[t]) break;
            }
        }
    }
}

void Init() {//v' = v + n
    cin >> n >> m;
    ZKW :: s = 0; ZKW :: t = n * 2 + 1;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) AddEdge(0, i, 1, 0);
    for (int i = 1; i <= n; i++) AddEdge(i + n, n * 2 + 1, 1, 0);
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        if (v < u) swap(v, u);
        if (w < a[v]) AddEdge(u, v + n, 1, w);
    }
    for (int i = 1; i <= n; i++) AddEdge(0, i + n, 1, a[i]);
}

void Work() {
    ZKW :: Work();
    cout << ZKW :: ans << endl;
}

int main() {
    Init();
    Work();
    return 0;
}
/*
3 3
1 100 100
2 1 10
1 3 1
2 3 1
*/
/*
3 3
1 2 3
1 2 100
1 3 100
2 3 100
*/
/*
4 5
100 1000 10 100
1 2 100
2 3 100
4 3 100
1 3 20
2 4 20
*/

LGOJ-P4043

传送门

解题思路

考虑到每走一条剧情有耗时,想要耗时最少走完所有剧情,考虑使用带权最小路径覆盖,费用流。

代码

// luogu-judger-enable-o2
#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

const int MAXN = 605;
const int INF = 0x3f3f3f3f;

int n;
int k[MAXN], dif[MAXN];

namespace CostFlow{
    struct Edge{
        int to, val, cost;
        Edge *nxt, *ops;

        Edge() {}

        Edge(int to, int val, int cost, Edge *nxt) : to(to), val(val), cost(cost), nxt(nxt) {}
    };

    Edge *head[MAXN], *cur[MAXN];

    void AddEdge(int u, int v, int w, int c) {
        head[u] = new Edge(v, w, c, head[u]);
        head[v] = new Edge(u, 0, -c, head[v]);
        head[u]->ops = head[v]; head[v]->ops = head[u];
    }

    int dis[MAXN], vis[MAXN], s, t, res, ans;

    int Spfa() {
        memset(vis, 0, sizeof(vis));
        memset(dis, INF, sizeof(dis));
        queue<int> q; q.push(s); dis[s] = 0; vis[s] = 1;
        while (!q.empty()) {
            int u = q.front(); q.pop(); vis[u] = 0;
            for (Edge *e = head[u]; e; e = e->nxt) {
                int v = e->to;
                if (dis[v] > dis[u] + e->cost && e->val) {
                    dis[v] = dis[u] + e->cost;
                    if (!vis[v]) {
                        vis[v] = 1;
                        q.push(v);
                    }
                }
            }
        }
        for (int i = 0; i <= n + 2; i++) cerr << dis[i] << ' ';
        cerr << endl;
        return dis[t] < INF;
    }

    int Dfs(int u, int flow) {
        if (u == t) {
            vis[u] = 1;
            res += flow;
            return flow;
        }
        vis[u] = 1;
        int used = 0;
        for (Edge *&e = cur[u]; e; e = e->nxt) {
            int v = e->to;
            if ((v == t || !vis[v]) && e->val && dis[v] == dis[u] + e->cost) {
                int mi = Dfs(v, min(flow - used, e->val));
                if (mi) {
                    e->val -= mi;
                    e->ops->val += mi;
                    used += mi;
                    ans += mi * e->cost;
                }
                if (used == flow) break;
            }
        }
        vis[u] = 0;
        return used;
    }

    void Zkw() {
        res = 0; ans = 0;
        while (Spfa()) {
            while (true) {
                memset(vis, 0, sizeof(vis));
                memcpy(cur, head, sizeof(head));
                Dfs(s, INF);
                if (!vis[t]) break;
            }
        }
    }
}

using CostFlow :: AddEdge;

void Init() {
    cin >> n;
    CostFlow :: s = 0;
    CostFlow :: t = n + 1;
}

void Work() {
    int tot = 0;
    AddEdge(n + 1, 0, INF, 0);
    for (int i = 1; i <= n; i++) {
        cin >> k[i];
        for (int j = 1; j <= k[i]; j++) {
            int b, t;
            cin >> b >> t;
            tot += t;
            AddEdge(i, b, INF, t);
            dif[i]--; dif[b]++;
        }
    }
    for (int i = 2; i <= n; i++) AddEdge(i, 1, INF, 0);
    for (int i = 1; i <= n; i++) {
        if (dif[i] > 0) AddEdge(0, i, dif[i], 0);
        if (dif[i] < 0) AddEdge(i, n + 1, -dif[i], 0);
    }
    CostFlow :: Zkw();
    cerr << CostFlow :: res << endl;
    cerr << CostFlow :: ans << endl;
    cerr << tot << endl;
    cout << CostFlow :: ans + tot << endl;
}

int main() {
    Init();
    Work();
    return 0;
}
/*
6
2 2 1 3 2
2 4 3 5 4
2 5 5 6 6
0
0
0
*/

LGOJ-P3749

传送门

解题思路

想要收益最大,根据数据范围,考虑网络流。最大流=最小割

具体建图细节较多,看代码

代码

// luogu-judger-enable-o2
// luogu-judger-enable-o2
#include <iostream>
#include <queue>
#include <string.h>

using namespace std;

typedef long long LL;

const int MAXN = 105;
const int MAXA = 1005;
const int INF = 0x3f3f3f3f;

int n, m;
int a[MAXN], d[MAXN][MAXN], idd[MAXN][MAXN];
int ida[MAXA], idcnt;
LL sum = 0;

namespace MaxFlow{
    const int MAXN = 1e2 + 1e3 + 1e4 + 5;

    struct Edge{
        int to, val;
        Edge *nxt, *ops;

        Edge(int to, int val, Edge *nxt) : to(to), val(val), nxt(nxt) {}
    };

    Edge *head[MAXN];
    int s, t, dep[MAXN], gap[MAXN], res, tot;

    void AddEdge(int u, int v, int w) {
        head[u] = new Edge(v, w, head[u]);
        head[v] = new Edge(u, 0, head[v]);
        head[u]->ops = head[v]; head[v]->ops = head[u];
    }

    void BFS() {
        memset(dep, -1, sizeof(dep));
        memset(gap, 0, sizeof(gap));
        dep[t] = 0; gap[dep[t]]++;
        queue<int> q; q.push(t);
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (Edge *e = head[u]; e; e = e->nxt) {
                int v = e->to;
                if (dep[v] != -1) continue;
                dep[v] = dep[u] + 1;
                gap[dep[v]]++;
                q.push(v);
            }
        }
    }

    int DFS(int u, int flow) {
        if (u == t) {
            res += flow;
            return flow;
        }
        int used = 0;
        for (Edge *e = head[u]; e; e = e->nxt) {
            int v = e->to;
            if (e->val && dep[v] == dep[u] - 1) {
                int mi = DFS(v, min(e->val, flow - used));
                if (mi) {
                    used += mi;
                    e->val -= mi;
                    e->ops->val += mi;
                }
                if (used == flow) return used;
            }
        }
        gap[dep[u]]--;
        if (gap[dep[u]] == 0) dep[s] = tot + 1;
        dep[u]++;
        gap[dep[u]]++;
        return used;
    }

    void ISAP() {
        res = 0;
        BFS();
        cerr << '*';
        while (dep[s] <= tot) DFS(s, INF);
    }
}

using MaxFlow :: AddEdge;

void Init() {
    cin >> n >> m;
    idcnt = n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        if (!ida[a[i]]) ida[a[i]] = ++idcnt;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j++) {
            cin >> d[i][j];
            idd[i][j] = ++idcnt;
        }
    }
}

void BuildGraph() {
    int S = MaxFlow :: s = 0;
    int T = MaxFlow :: t = idcnt + 1;
    MaxFlow :: tot = idcnt + 2;
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j++) {
            if (d[i][j] > 0) {
                AddEdge(S, idd[i][j], d[i][j]);
                sum += d[i][j];
            } else if (d[i][j] < 0) {
                AddEdge(idd[i][j], T, -d[i][j]);
            }
        }
    }
    for (int i = 1; i <= n; i++)
        for (int j = i; j <= n; j++)
            for (int k = i; k <= j; k++)
                AddEdge(idd[i][j], k, INF);
    for (int i = 1; i < MAXA; i++) {
        if (ida[i]) AddEdge(ida[i], T, m * i * i);
    }
    for (int i = 1; i <= n; i++) AddEdge(i, ida[a[i]], INF);
    for (int i = 1; i <= n; i++) AddEdge(i, T, a[i]);
    for (int i = 1; i < n; i++) {
        for (int j = i + 1; j <= n; j++) {
            AddEdge(idd[i][j], idd[i][j - 1], INF);
            AddEdge(idd[i][j], idd[i + 1][j], INF);
        }
    }
}

void Work() {
    BuildGraph();
    cerr << '*';
    MaxFlow :: ISAP();
    cout << sum - MaxFlow :: res << endl;
}

int main() {
    Init();
    Work();
    return 0;
}
/**/

LGOJ-P2151

传送门

解题思路

考虑到边数少,并且有特殊要求,可以以时间和边作为状态来动规,转移很好想。

考虑到时间范围较大,应该采用矩阵优化

代码

// luogu-judger-enable-o2
// luogu-judger-enable-o2
#include <iostream>
#include <cstring>

using namespace std;

const int MAXN = 55;
const int MAXM = 125;
const int MOD = 45989;

int n, m, t, st, ed;
int u[MAXM], v[MAXM], cnt = -1;

struct Matrix{
    int a[MAXM][MAXM];

    Matrix() {
        memset(a, 0, sizeof(a));
    }

    void Init() {
        memset(a, 0, sizeof(a));
        for (int i = 0; i < m; i++) a[i][i] = 1;
    }
};

Matrix operator * (const Matrix &a, const Matrix &b) {
    Matrix ret;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < m; j++) {
            for (int k = 0; k < m; k++) {
                ret.a[i][j] = (ret.a[i][j] + a.a[k][j] * b.a[i][k] % MOD) % MOD;
            }
        }
    }
    return ret;
}

Matrix operator ^ (const Matrix &a, int b) {
    Matrix base = a, ret;
    ret.Init();
    while (b) {
        if (b & 1) ret = ret * base;
        b >>= 1;
        base = base * base;
    }
    return ret;
}

void Debug(const Matrix &o) {
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < m; j++) {
            cerr << o.a[i][j] << ' ';
        }
        cerr << endl;
    }
}

void Init() {
    cin >> n >> m >> t >> st >> ed;
    int x, y;
    for (int i = 1; i <= m; i++) {
        cin >> x >> y;
        cnt++;
        u[cnt] = x; v[cnt] = y;
        cnt++;
        u[cnt] = y; v[cnt] = x;
    }
    m <<= 1;
}

void Work() {
    Matrix mxa, mxb, mxc;
    for (int i = 0; i < m; i++) {
        if (u[i] == st) mxa.a[i][0] = 1;
    }
//    cerr << "###" << endl;
//    for (int i = 0; i < m; i++) cerr << u[i] << ' ';
//    cerr << endl;
//    for (int i = 0; i < m; i++) cerr << v[i] << ' ';
//    cerr << endl << "###" << endl;
//    Debug(mxa);
//    cerr << "###" << endl;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < m; j++) {
            if (j == (i ^ 1)) continue;
            if (v[i] == u[j]) {
//                cerr << '*';
                mxb.a[j][i] = 1;
            }
        }
    }
//    Debug(mxb);
//    cerr << "###" << endl;
    mxc = mxa * (mxb ^ (t - 1));
//    mxc = mxa * mxb;
//    Debug(mxc);
//    cerr << "###" << endl;
//    mxc = mxc * mxb;
//    Debug(mxc);
//    cerr << "###" << endl;
    int ans = 0;
    for (int i = 0; i < m; i++) {
        if (v[i] == ed) ans = (ans + mxc.a[i][0]) % MOD;
    }
    cout << ans << endl;
}

int main() {
    Init();
    Work();
    return 0;
}
/*
4 5 3 0 0
0 1
0 2
0 3
2 1
3 2
*/