题目描述：

n个人比赛, 每人都要和其余的比一场, 打败一个人得一分, 如果一个人打败了所有比自己分数高的人, 或者他本身就是分数最高的, 那么他就是Strong King, 可能有多个Strong King, 现在按非降的顺序给你每个人的得分, 问Strong King最多能有几个. n<=10.

解题报告： 转自：http://www.answeror.com/archives/27184

这是个很有意思的网络流, 题目中告诉你n<=10就是在暗示可能需要枚举, 枚举什么呢? 按以往做过的网络流题目中的惯例, 只要出现"最小的最大", "最大的最小"之类的字眼肯定就是二分答案, 这次也不例外, 只是二分变成了纯枚举.

这题建图的方法很巧妙. 设n个人得分按非降顺序排列为序列a, 首先肯定要设一个源点, 一个汇点, 在用最大流判可行性的题目中, 源点到其它顶点的弧的权值往往表示需要满足的值, 然后求出最大流跟这些值的和相比较. 那么不妨设n个顶点表示n个人, 源点向每个人连一条权值为a[i]的弧.

接下来撇开Strong King的个数不看, 我们想想比赛需要满足什么条件, 显然是每场比赛肯定有两个人参与, 但是有且只有一个人胜出, 想到什么了吗? 两条流流进来, 只有一条出去…

如果能想到将每场比赛也作为顶点就好办了, 把每个人往每场自己参与过的比赛都连一条权值为1的弧, 然后每场比赛都往汇点连一条权值为1的弧, 这就把"二选一"的要求完美地用一张图表示出来了.

那么Strong King怎么办? 假设有k个Strong King, 那么他们一定是得分最高的k个人, 并且每个人都把得分比自己高的人打败了, 怎么在图中表示A一定打败B呢? 让B退出比赛呗. 把B连向这场比赛的弧去掉, OK, A必胜了.

接下来就随便套套模板好了.

注意这题的输入非常恶心, 数字间的空格数是任意的, 行尾有任意多的空格, 最后一行可能没有换行…只有一点可以确定, 没有连续的换行.

代码如下：

#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<algorithm>
using namespace std;
int t, jeo[10], n;
string x[10];
#define Max 0x1fffffff
#define size 500
struct edge{int from, to, val, next;}e[140000];
int v[size], que[size], dis[size], cnt, cur[size];
void insert(int from, int to, int va)
{
    e[cnt].from = from, e[cnt].to = to; e[cnt].val = va;
    e[cnt].next = v[from];v[from] = cnt++;
    e[cnt].from = to, e[cnt].to = from; e[cnt].val = 0;
    e[cnt].next = v[to];v[to] = cnt++;
}
bool bfs(int n, int s, int t)
{
    int head, tail, id;
    head = tail = 0; que[tail++] = s;
    memset(dis, -1, sizeof(int) * n);dis[s] = 0;
    while(head < tail) // bfs,得到顶点i的距s的最短距离dis[i]
        for(id = v[que[head++]]; id != -1; id = e[id].next)
            if (e[id].val > 0 && dis[e[id].to] == -1)
            {
                dis[e[id].to] = dis[e[id].from] + 1;
                que[tail++] = e[id].to;
                if (e[id].to == t) return true;
            }
    return false;
}
int Dinic(int n, int s, int t)
{
    int maxflow = 0, tmp, i;
    while(bfs(n, s, t))
    {
        int u = s, tail = 0;
        for(i = 0; i < n; i++) cur[i] = v[i];
        while(cur[s] != -1)
            if (u != t && cur[u] != -1 && e[cur[u]].val > 0 && dis[u] != -1 && dis[u] + 1 == dis[e[cur[u]].to])
            {que[tail++] = cur[u]; u = e[cur[u]].to;}
            else if (u == t)
            {
                for(tmp = Max, i = tail - 1; i >= 0; i--) tmp = min(tmp, e[que[i]].val);
                for(maxflow += tmp, i = tail - 1; i >= 0; i--)
                {
                    e[que[i]].val -= tmp;
                    e[que[i] ^ 1].val += tmp;
                    if (e[que[i]].val == 0) tail = i;
                }
                u = e[que[tail]].from;
            }
            else
            {
                while(tail > 0 && u != s && cur[u] == -1) u = e[que[--tail]].from;
                cur[u] = e[cur[u]].next;
            }
    }
    return maxflow;
}
void input()
{
    for(int i = 0; i < 10; i++) x[i] = "";
    char c; n = -1;
    while(true)
    {
        bool flag = true;
        while((c = getchar()) != ' ')
        {
            if (c == '\n')
            {
                n++;
                for(int i = 0; i < n; i++)
                    sscanf(x[i].c_str(), "%d", &jeo[i]);
                return;
            }
            if (flag) flag = false, n++;
            x[n] += c;
        }
    }
}
bool cmp(int a, int b){return a > b;}
int main()
{
    scanf("%d", &t);getchar();
    while(t--)
    {
        input();
        int ans = 0; sort(jeo, jeo + n, cmp);
        for(int i = 0; i < n; i++)
        {
            int s = n, t = n + n * (n - 1) / 2 + 1;
            memset(v, -1, sizeof(int) * (t + 1)); cnt = 0;
            for(int j = 0; j < n; j++) insert(s, j, jeo[j]);
            for(int j = 0, num = 0; j < n; j++)
                for(int k = j + 1; k < n; k++)
                {
                    num++; insert(n + num, t, 1);
                    if (jeo[j] > jeo[k] && k <= i) insert(k, n + num, 1);
                    else insert(j, n + num, 1), insert(k, n + num, 1);
                }
            if (Dinic(t + 1, s, t) >= n * (n - 1) / 2) ans = i + 1;
        }
        printf("%d\n", ans);
    }
    return 0;
}