这题其实不难想到

Description

link

题意太长了，概括不来，去题库里扫一眼吧（但是很好懂）

Solution

\[Begin
\]

考虑一个事情：每一个队伍的输局是没有用的

贪心一下，让每个队伍把剩下的比赛赢下来的时候，最有可能夺冠

设最终当前队赢得的场数的 $maxx$

接下来我们考虑让剩下的比赛怎么胜负

非这个队在剩下的比赛中的最大胜场数不得大于 $maxx-w_j$ ，其中$j \in[1,n] $且 $j!=i$

然后我们建图

每一场比赛都会让胜者的胜利场次加 $1$ ,把比赛的场次当成一个点，队伍当成一个点

每场比赛向队伍分别连边，边权为 $1$ ，源点向比赛场次连，然后队伍向汇点连

跑网络流就行了（或者这玩意就是个二分图完美匹配？？）

\[Finish
\]

Code

#include <bits/stdc++.h>

using namespace std;

#define int long long

#define cl(x) memset(x, 0, sizeof(x))

namespace yspm {

inline int read() {

    int res = 0, f = 1;

    char k;

    while (!isdigit(k = getchar()))

        if (k == '-')

            f = -1;

    while (isdigit(k)) res = res * 10 + k - '0', k = getchar();

    return res * f;

}

int n, s, t, tot;

const int N = 1e4 + 10;

int head[N], w[N], a[N][N], id[N][N], dep[N], cnt = 1;

struct node {

    int nxt, to, lim;

} e[N << 1];

inline void add2(int u, int v, int w) {

    e[++cnt].lim = w;

    e[cnt].nxt = head[u];

    e[cnt].to = v;

    return head[u] = cnt, void();

}

inline void add1(int u, int v, int w) {

    add2(u, v, w);

    add2(v, u, 0);

    return;

}

queue<int> q;

inline bool bfs() {

    cl(dep);

    dep[s] = 1;

    q.push(s);

    while (q.size()) {

        int fr = q.front();

        q.pop();

        for (int i = head[fr]; i; i = e[i].nxt) {

            int t = e[i].to;

            if (!dep[t] && e[i].lim)

                dep[t] = dep[fr] + 1, q.push(t);

        }

    }

    return dep[t];

}

inline int dfs(int now, int in) {

    if (now == t)

        return in;

    for (int i = head[now]; i && in; i = e[i].nxt) {

        int t = e[i].to;

        if (!e[i].lim || dep[t] != dep[now] + 1)

            continue;

        int res = dfs(t, min(e[i].lim, in));

        e[i].lim -= res;

        e[i ^ 1].lim += res;

        if (res)

            return res;

    }

    return 0;

}

inline void solve(int x) {

    cl(head);

    cnt = 1;

    cl(e);

    int maxx = w[x], tmp = 0;

    for (int i = 1; i <= n; ++i) maxx += a[x][i];

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

        if (i == x)

            continue;

        if (w[i] > maxx)

            return;

        add1(i, t, maxx - w[i]);

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

            if (j != x && a[i][j]) {

                add1(s, id[i][j], a[i][j]), tmp += a[i][j];

                add1(id[i][j], i, a[i][j]);

                add1(id[i][j], j, a[i][j]);

            }

        }

    }

    int sum = 0, d;

    while (bfs()) {

        while (d = dfs(s, 1e15 + 10)) sum += d;

    }

    if (sum == tmp)

        printf("%lld ", x);

    return;

}

signed main() {

    n = read();

    s = n + 1, t = n + 2, tot = n + 2;

    for (int i = 1, k; i <= n; ++i) w[i] = read(), k = read();

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

        for (int j = 1; j <= n; ++j) a[i][j] = read();

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

        for (int j = 1; j < i; ++j) id[i][j] = ++tot;

    for (int i = 1; i <= n; ++i) solve(i);

    puts("");

    return 0;

}

}  // namespace yspm

signed main() { return yspm::main(); }

格式化了，代码很好懂

巴特西

LGOJ1264 K-联赛

Description

Solution

Code

最新文章

热门文章