题目链接

题意

对于一个竞赛图（有向完全图），其顶点是选手，边是比赛，边\(e=(u,v)\)代表该场比赛中\(u\)战胜\(v\)。

现定义选手的分数为其战胜的人的个数（即竞赛图中点的出度）。并且定义\(strong\ king\)为这样的选手，他战胜了所有比他分数高的人。

给定各选手的分数序列，问这个分数序列对应的所有可能的比赛局面中，最多有多少个\(strong\ king\)？

思路

从定义着手——建图

\(strong\ king\)为这样的选手，他战胜了所有比他分数高的人

这意味着什么？

这意味着对于所有发生在\(u,v\)之间的比赛，如果\(u\)是\(strong\ king\)并且\(score(u)<score(v)\)，那么在原竞赛图中有边\((u,v)\)（即\(u\)战胜\(v\)），对\(u\)的分数的贡献为\(1\).

那么可不可以拆点建图呢？拆成胜者和败者？

不可以，因为无法保证边\((u,v)\)和边\((v,u)\)不共存。

此时注意到，选手与比赛之间的关系是可以通过限制保证其唯一性的，于是如下建图：

在源点到选手(\(n\)个) 之间连边，边权为选手的分数
在比赛(\(\frac{n*(n-1)}{2}场\)) 到汇点之间连边，边权为\(1\)
在选手\(i,j\) 到发生在\(i,j\)间的比赛之间连边：

如果确定某个人赢了这场比赛，那么就连确定的一条边，否则两条都连。

然而，我怎么知道谁赢了这场比赛呢？

即，哪些比赛的结果是确定的呢？

也就是，哪些人是\(strong\ king\)呢？

提供建图的条件——枚举

注意到，\(n\leq 10\)，于是可以考虑从大到小枚举\(strong\ king\)的个数\(k\)。

对于每一个\(k\)，再去枚举其每一个子集，在此基础上建图进行\(check\).

如果有一个子集可以满流，就意味着这个\(k\)是可行的。

一个巧妙的结论——优化

事实上，对于每一个\(k\)，可以不用枚举其每一个子集，而只要看分数最高的\(k\)个人，令他们皆为\(strong\ king\)然后建图。

结论

如果该分数序列可以对应到一个有\(k\)名\(strong\ king\)的比赛局面，那么必然存在这样一个局面，其中

\(k\)名\(strong\ king\)为分数最高的\(k\)人。

证明

采用逐步调整法。

假设存在一个有\(k\)名\(strong\ king\)的局面，但他们并不是连续的分数最高的k人，则存在\(i,j, score(i) < score(j)\), \(i\)是\(strong\ king\)而\(j\)不是。

这意味着在分数高于\(i\)的人中存在\(t\)个人，\(x_1,x_2,...,x_t\)，\(i\)未战胜他们，而\(j\)战胜了他们。

现进行调整，使得\(i\)战胜了\(x_1,x_2,...,x_t\)，\(j\)未战胜\(x_t\)，则

\(i\)的分数增加了\(t\)
\(j\)的分数减少了\(1\)
\(x_t\)的分数守恒
\(x_1,x_2,...x_{t-1}\)的分数均减少了\(1\)

于是在分数不大于\(i\)的人的范围内，再找\(t\)个人，满足\(i\)战胜了他们，而\(j,x_1,x_2,...,x_{t-1}\)未战胜他们。反转这些局面，即可使得所有分数守恒。

// 至于是否能够找到这\(t\)个人，我暂时并不会证...Orz

Code

#include <cstdio>

#include <cstring>

#include <queue>

#include <iostream>

#define maxn 1010

#define inf 0x3f3f3f3f

using namespace std;

typedef long long LL;

struct Edge { int to, ne, c; }edge[maxn];

int dep[maxn], ne[maxn], n,tot, s,t, a[maxn];

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

    edge[tot] = {v, ne[u], c};

    ne[u] = tot++;

    edge[tot] = {u, ne[v], 0};

    ne[v] = tot++;

}

int bfs(int src) {

    memset(dep, 0, sizeof dep);

    dep[src] = 1;

    queue<int> q;

    while (!q.empty()) q.pop();

    q.push(src);

    while (!q.empty()) {

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

        for (int i = ne[u]; ~i; i = edge[i].ne) {

            int v = edge[i].to;

            if (edge[i].c > 0 && !dep[v]) dep[v] = dep[u] + 1, q.push(v);

        }

    }

    return dep[t];

}

int dfs(int u, int flow) {

    if (u == t) return flow;

    int ret = 0;

    for (int i = ne[u]; ~i; i = edge[i].ne) {

        int v = edge[i].to;

        if (edge[i].c > 0 && dep[v] == dep[u] + 1) {

            int c = dfs(v, min(flow-ret, edge[i].c));

            edge[i].c -= c;

            edge[i^1].c += c;

            ret += c;

            if (ret == flow) break;

        }

    }

    if (!flow) dep[u] = 0;

    return ret;

}

bool getInt(int& x) {

    char ch = getchar();

    while (!isdigit(ch)) {

        if (ch=='\n') return false;

        ch = getchar();

    }

    x = ch-'0';

    return true;

}

bool tryy(int x) {

    tot=0; memset(ne,-1,sizeof(ne));

    s=0, t=n+n*(n-1)/2+1;

    for (int i = 1; i <= n; ++i) add(s, i, a[i]);

    for (int i = 1; i <= n*(n-1)/2; ++i) add(n+i, t, 1);

    int u=1, v=2;

    for (int i = 1; i <= n*(n-1)/2; ++i) {

        if (u >= x && a[v] > a[u]) add(u, n+i, 1);

        else add(u, n+i, 1), add(v, n+i, 1);

        ++v; if (v==n+1) v = ++u+1;

    }

    int ans=0, ret=0;

    while (bfs(s)) {

        while (ret = dfs(s, inf)) ans += ret;

    }

    return ans == n*(n-1)/2;

}

void work() {

    n = 0; while (getInt(a[++n])); --n;

    for (int i = n; i >= 1; --i) if (tryy(n-i+1)) {

        printf("%d\n", i); return;

    }

}

int main() {

    int T;

    scanf("%d\n", &T);

    while (T--) work();

    return 0;

}

后话

其实我有些迷茫，不是很清楚博客写得这么详尽有多大的意义...

更何况，这个方法还并不是自己想出来的而是看了别人的博客得到的...

并且，有写这些的时间其实可以用来再写一道题了...

但是怎么说呢...

在写博客的时候，在理思路与组织文字的时候，事实上是有反思这个思考的过程的。

一步一步写下来，就觉得是个很顺畅的思路了，是应当且能够想出来的。

毕竟，做题不仅是积累经验，更重要的是训练思维啊。

但愿这是有用的吧。

还请大家多多批评指正。

一起变得更加强吧。

巴特西

poj 2699 The Maximum Number of Strong Kings 枚举最大流

题目链接

题意

思路

从定义着手——建图

提供建图的条件——枚举

一个巧妙的结论——优化

结论

证明

Code

后话

最新文章

热门文章

巴特西

poj 2699 The Maximum Number of Strong Kings 枚举 最大流

题目链接

题意

思路

从定义着手——建图

提供建图的条件——枚举

一个巧妙的结论——优化

结论

证明

Code

后话

最新文章

热门文章

poj 2699 The Maximum Number of Strong Kings 枚举最大流