最大流。枚举可能是strong king的人数。
把人数和每场比赛(共n * (n - 1) / 2场)抽象成点。
建图时:(1)从源点到每个人连流量为score[i]的边;
(2)从每场比赛到汇点连流量为1的边;
(3)如果score[i] > score[j], 则i和j的比赛只能由j获胜,连j到i和j对应比赛的流量为1的边,否则谁获胜都可以,分别连i和j到他们对应比赛的流量为1的边。
最后看建好图之后的最大流是不是n * (n - 1) / 2。如果是,则说明这个k是可以的。
#include <iostream> #include <cstdio> #include <sstream> #include <cstring> #include <string> #include <cmath> #include <vector> #include <queue> #include <map> #include <set> #include <list> #include <algorithm> #include <functional> #define sz(v) ((int)(v).size()) #define rep(i, n) for(int i = 0; i < n; i++) #define repf(i, a, b) for(int i = a; i <= b; i++) #define out(n) printf("%d\n", n) #define mset(a, b) memset(a, b, sizeof(a)) #define lint long long using namespace std; const int INF = 1 << 30; const int MaxN = 1005; struct NetWork { struct Adj { int v, c, b; Adj() {} Adj(int _v, int _c, int _b) : v(_v), c(_c), b(_b) {} }; int n, s, t, h[MaxN], cnt[MaxN]; vector<Adj> adj[MaxN]; void clear() { for(int i = 0; i < n; i++) { adj[i].clear(); } n = 0; } void add_edge(int u, int v, int c) { n = max( n, max(u, v) + 1 ); adj[u].push_back(Adj(v, c, adj[v].size())); adj[v].push_back(Adj(u, 0, adj[u].size() - 1)); } int max_flow(int _s, int _t) { s = _s, t = _t; fill(h, h + n, 0); fill(cnt, cnt + n, 0); int flow = 0; while(h[s] < n) { flow += dfs(s, INF); } return flow; } int dfs(int u, int flow) { if(u == t) return flow; int minh = n - 1, ct = 0; for(vector<Adj>::iterator it = adj[u].begin(); flow && it != adj[u].end(); it++) { if(it->c) { if(h[it->v] + 1 == h[u]) { int k = dfs(it->v, min(it->c, flow)); if(k) { it->c -= k; adj[it->v][it->b].c += k; flow -= k; ct += k; } if(h[s] >= n) return ct; } minh = min(minh, h[it->v]); } } if(ct) return ct; if(--cnt[ h[u] ] == 0) h[s] = n; h[u] = minh + 1; ++cnt[h[u]]; return 0; } }network; int score[15]; int n, m; string s; int gao() { m = n * (n - 1) / 2; int ans = 0; int s = n + m + 1; int t = s + 1; for(int k = 0; k <= n; k++) { network.clear(); for(int i = 1; i <= n; i++) { network.add_edge(s, i, score[i]); } int num = 0; for(int i = 1; i <= n; i++) { for(int j = i + 1; j <= n; j++) { num++; network.add_edge(num + n, t, 1); if(i > n - k && score[j] > score[i]) { network.add_edge(i, num + n, 1); } else { network.add_edge(i, num + n, 1); network.add_edge(j, num + n, 1); } } } if(network.max_flow(s, t) == m) { ans = k; } else break; } return ans; } int main() { int t; scanf("%d", &t); getchar(); while(t--) { getline(cin, s); istringstream sin(s); int tmp; n = 0; while(sin >> tmp) { score[++n] = tmp; } out(gao()); } return 0; }