[TJOI 2018]智力竞赛

Description

题库链接

给出一张 \(m\) 个点的有向图。问可重最小路径覆盖是否 \(\leq n+1\) 。若不，求最多用 \(n+1\) 条路径去覆盖，最大化未覆盖点点权最小值。

\(1\leq n\leq 50,1\leq m\leq 500\)

Solution

\(\text{floyd}\) 传递闭包之后做最小路径覆盖...

若无解，考虑二分未覆盖点点权最小值，将点权小于 \(mid\) 的点加入图中做最小路径覆盖。

写这题其实是打 \(\text{dinic}\) 板子的...

Code

#include <bits/stdc++.h>

using namespace std;

const int N = 500+5, inf = ~0u>>1;

int n, m, G[N][N], v[N], k, u;

struct tt {int to, next, cap; }edge[N*N<<1];

int path[N<<1], top, S = (N<<1)-2, T = (N<<1)-1;

int sta[N<<1], cur[N<<1], dist[N<<1];

queue<int>Q;

bool bfs() {

    memset(dist, -1, sizeof(dist));

    Q.push(S); dist[S] = 1;

    while (!Q.empty()) {

        int u = Q.front(); Q.pop();

        for (int i = path[u], v; ~i; i = edge[i].next)

            if (dist[v = edge[i].to] == -1 && edge[i].cap > 0)

                Q.push(v), dist[v] = dist[u]+1;

    }

    return dist[T] != -1;

}

int dinic() {

    int totflow = 0;

    while (bfs()) {

        int u = S; top = 0; memcpy(cur, path, sizeof(cur));

        while (1) {

            if (u == T) {

                int loc, minflow = inf;

                for (int i = 1; i <= top; i++) if (edge[sta[i]].cap < minflow) minflow = edge[sta[loc = i]].cap;

                for (int i = 1; i <= top; i++) edge[sta[i]].cap -= minflow, edge[sta[i]^1].cap += minflow;

                totflow += minflow; u = edge[sta[loc]^1].to, top = loc-1;

            }

            for (int &i = cur[u], v; ~i; i = edge[i].next)

                if (dist[v = edge[i].to] == dist[u]+1 && edge[i].cap > 0) {

                    sta[++top] = i, u = v; break;

                }

            if (cur[u] == -1) {

                if (top == 0) break;

                dist[u] = -inf; u = edge[sta[top--]^1].to;

            }

        }

    }

    return totflow;

}

void add(int u, int v, int c) {

    edge[++top] = (tt){v, path[u], c}; path[u] = top;

    edge[++top] = (tt){u, path[v], 0}; path[v] = top;

}

bool judge(int mid) {

    memset(path, top = -1, sizeof(path)); int cnt = 0;

    for (int i = 1; i <= m; i++) add(S, i, 1), add(i+N-5, T, 1);

    for (int i = 1; i <= m; i++)

        if (v[i] < mid) {

            ++cnt;

            for (int j = 1; j <= m; j++)

                if (v[j] < mid && G[i][j])

                    add(i, j+N-5, 1);

        }

    return cnt-dinic() <= n+1;

}

void work() {

    scanf("%d%d", &n, &m);

    for (int i = 1; i <= m; i++) {

        scanf("%d%d", &v[i], &k);

        for (int j = 1; j <= k; j++) scanf("%d", &u), G[i][u] = 1;

    }

    for (int k = 1; k <= m; k++)

        for (int i = 1; i <= m; i++)

            for (int j = 1; j <= m; j++)

                G[i][j] |= (G[i][k]&G[k][j]);

    if (judge(1000000000+1)) {puts("AK"); return; }

    int L = 0, R = 1e9, ans;

    while (L <= R) {

        int mid = (L+R)>>1;

        if (judge(mid)) ans = mid, L = mid+1;

        else R = mid-1;

    }

    printf("%d\n", ans);

}

int main() {work(); return 0; }

巴特西

[TJOI 2018]智力竞赛

Description

Solution

Code

最新文章

热门文章