poj 2699 The Maximum Number of Strong Kings sap算法

缘起

继续浪费生命~ poj 2699 The Maximum Number of Strong Kings

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
题意的话，就是有n 个人，两两之间打比赛，每场比赛赢的人加一分，总共呢有n*(n-1)/2个比赛，
然后求这样一种人(这种人叫做Strong Kings)的个数，就是能赢所有比自己分高的人或者他就是分最高的人.
当然我们是求这种人可能的最大个数.

【输入】
多样例.第一行是样例数。 每个样例就是一个序列（最多10个数,即最多10位选手）, 就是这些人的得分.

【输出】
输出strong kings的最大个数

【样例输入】
5
1 2 2 2 3
1 1 3 4 4 4 4
3 3 4 4 4 4 5 6 6 6
0 3 4 4 4 5 5 5 6
0 3 3 3 3 3

【样例输出】
2
4
5
3
5

【限制】
1s

此题是想法题. 最暴力的做法是这样的——因为选手数量n不超过10位. 所以完全可以二进制压缩进行暴力枚举k位最强王者（1<=k<=n）. 然后网络流建图. 两类点. 一类是选手, 一类是比赛. 然后建立炒鸡源，炒鸡汇. 炒鸡源到选手的弧容量显然就是选手的得分. 然后比赛到炒鸡汇的弧的容量是1，表示每场比赛只能有一位胜者. 然后我们来考虑每位选手和比赛之间的弧. 显然, 对于有最强王者参与的比赛，我们必须慎重考虑. 首先，最强王者能连的比赛一定是n-1场, 即它参与的比赛. 假设最强王者是i, 它参与的比赛\<i,j>, 那么i能连这场比赛对应的点吗? 如果j得分比i高的话, 由最强王者的定义就知道, j是不能连这个比赛对应点的. 而只能i去连(弧的容量是1). 因为这场比赛的胜负一定是i获胜. 而对于其他情况的话, i和j都可以去连接这场比赛. 弧的容量都是1.

然后跑最大流. 如果满流的话, 就表明存在一种可行流不仅满足所有选手的得分, 而且还能保证你选的那k位都是最强王者——为什么? 因为所有选手的得分一定是比赛场次（因为每场比赛必然产生1分）， 所以只有一条弧连过来的比赛点的那条弧是一定要连的（不然就一定不满流）. 所以我们就知道k名最强王者是可以的. 即答案不会<k. 注意, 答案不具备单调性，不能使用二分答案（所幸的是n比较小）. 复杂度应该是 2^10*每次最大流的复杂度. 网上有人试过, 大约125ms左右能水过此题.

但是, 这是最好的姿势吗?

显然不是，从叙述就可以看出满满的冗余——别的不说——我就想知道最多能有几位最强王者，你为啥要枚举哪几位是最强王者? 这不是冗余吗? 遂我们诞生了下面的想法

枚举k, 然后断言，如果存在k位最强王者的话，则一定能将这k位最强王者移动到得分最高的那k位上去. 即我们可以假定这k位最强王者就是得分最高的那k位.

证明: 假设1,….,i,…,j, ….,k…,n 是按得分升序排序. i和k都是最强王者. j不是. 我们的目的是将j变成最强王者, 而i可能失去最强王者的资格——即我们已经成功的将最强王者的人往分数序列后面移动了.

假设j输给了j+1,…,n 中x名选手. 现在为了将j变成最强王者, 将这x场比赛的结果反转——则j变成最强王者了. 但是出现了2个问题

  1. j的得分多出了x分
  2. 后面x名选手的得分都少了1分

则因为i是最强王者, 所以i一定赢了这x名选手. 现在将这x名选手都赢i, 则这x名选手的得分就恢复了. 但是i的得分又少了x分. 此时, i得分少了x, j得分多了x. 所以只需要让j多输x场（因为j要变成最强王者, 所以j多输的这x场一定来自1,…j-1）. 而j多输的这些场的人(即这些人赢了j)，让i去赢他们. 则i失去的x分又回来了. 综上, j变成了最强王者, 而i未必是最强王者了. 我们将最强王者们整体向分数递增序列尾部移动了.

所以本题的复杂度会大为降低. 将分数序列递增排序, 枚举最强王者的数量k, 并且假设得分最高的k位选手就是最强王者. 然后按照上面说的那种策略建图, 具体讲就是

1
2
3
炒鸡源到n名选手的弧长度是选手的得分. n(n-1)/2场比赛到炒鸡汇的弧容量是1. 枚举 1<=k<=n(显然倒序)
选手i、j以及比赛<i,j>, 如果满足 n-k<i<j<=n, 则只能i去连接<i,j>，弧容量为1
其他所有情况, i和j都可以和<i,j>连接一条容量为1的弧.

然后跑最大流. 如果满流的话, 则表明k是可以的. 而且本题的输入比较恶心. 需要sscanf

下面的代码关于sap的没写注释, 不清楚的话, 看【1】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
//#include "stdafx.h"
#include <iostream>
#include <stdio.h>
#include <sstream>
#include <algorithm>
#include <string.h>
using namespace std;
//#define LOCAL

char s[100];
int n, a[15], head[55+15], cnt, t, gap[55+15], level[55+15], flow[55+15], pre[55+15];
struct Arc
{
	int from, to, nxt, cap;
}g[55*15+55+15<<1];

void addArc(int from, int to,int cap)
{
	g[cnt].from = from, g[cnt].to = to, g[cnt].nxt = head[from], g[cnt].cap = cap;
	head[from] = cnt++;
	g[cnt].from = to, g[cnt].to = from, g[cnt].nxt = head[to], g[cnt].cap = 0;
	head[to] = cnt++;
}

inline int game(int i, int j) // i和j比赛<i,j>的点的编号
{
	return n+(2*n-i)*(i-1)/2+j-i;
}

void build(int k) // 全部推倒重来, 不要怕耽误时间, 本题数据规模较小, 建图很快的
{
	memset(head, -1, sizeof(head));
	cnt = 0;
	for (int i = 1; i<=n; i++)
	{
		addArc(0,i,a[i]);
	} // 炒鸡源到选手的弧
	for (int i = n+1; i<t; i++)
	{
		addArc(i, t, 1);
	} // 比赛到炒鸡汇的弧
	for (int i = 1; i<n; i++)
	{
		for (int j = i+1; j<=n; j++) // 考虑比赛<i,j>
		{
			addArc(i, game(i,j), 1); // i和比赛连弧,容量为1
			if (i<=n-k || (i>n-k && a[i]==a[j])) // 如果不是最强王者局或者是最强王者局但是两者得分一样, 则j也可以连, 注意, 忘了得分一样这种情形, 结果wa
			{
				addArc(j, game(i,j), 1);
			}
		}
	} // 选手到比赛的弧
}

int feasible(int cur)
{
	for (int h = head[cur],to; ~h; h = g[h].nxt)
	{
		to = g[h].to;
		if (g[h].cap>0 && level[cur]==level[to]+1)
		{
			return h;
		}
	}
	return -1;
}

void updata(int s, int t, int d)
{
	int h;
	while(t!=s)
	{
		h = pre[t];
		g[h].cap-=d;
		g[h^1].cap+=d;
		t = g[h].from;
	}
}

int retreat(int cur)
{
	int ans = t+1;
	for (int h = head[cur], to; ~h; h = g[h].nxt)
	{
		to = g[h].to;
		if (g[h].cap>0 && ans>level[to]+1)
		{
			ans = level[to]+1;
		}
	}
	return ans;
}

int sap(int s, int t)
{
	memset(level, 0, sizeof(level));
	memset(gap, 0, sizeof(gap));
	int ans = 0, cur=s, nxtArc, nxt;
	flow[s] = 0x3f3f3f3f;
	while(level[s]<=t)
	{
		nxtArc = feasible(cur);
		if (~nxtArc)
		{
			nxt = g[nxtArc].to;
			pre[nxt] = nxtArc;
			flow[nxt] = min(flow[cur], g[nxtArc].cap);
			cur = nxt;
			if (cur==t)
			{
				ans+=flow[t];
				updata(s,t,flow[t]);
				cur = s;
			}
		}
		else
		{
			if (!--gap[level[cur]])
			{
				return ans;
			}
			gap[level[cur]=retreat(cur)]++;
			if (cur!=s)
			{
				cur = g[pre[cur]].from;
			}
		}
	}
	return ans;
}

bool ok(int k) // n-k+1,...,n 这k位选手都是最强王者
{
	build(k); // 重构图
	return n*(n-1)/2==sap(0, t); // 判断是否满流, 注意, a[0,...,n-1]之和一定等于n*(n-1)/2
}

int kk()
{
	for (int k = n; ~k; k--)
	{
		if (ok(k))
		{
			return k;
		}
	}
	return 0;
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//	freopen("d:\\my.out", "w", stdout);
#endif
	int kase;
	scanf("%d", &kase);
	getchar(); // 吸收多余换行符
	while(kase--)
	{
		stringstream ss;
		gets(s);
		ss<<s;
		n =1;
		while(ss>>a[n])n++; // 本题输入比较恶心, 最后 a[1,...,n]是升序排序的
		sort(a+1, a+n); // 升序排序
		n--;
		t = 1+n+(n*(n-1)>>1); // n名选手, n(n-1)/2场比赛, 这是炒鸡汇
		printf("%d\n", kk());
	}
	return 0;
}

ac情况

Status Accepted
Memory 204kB
Length 2860
Lang C++
Submitted 2019-09-29 15:45:55
Shared
RemoteRunId 20910274

【1】https://yfsyfs.github.io/2019/09/28/poj-2391-Ombrophobic-Bovines-%E4%BA%8C%E5%88%86-%E6%8B%86%E7%82%B9-floyd-%E6%9C%80%E5%A4%A7%E6%B5%81-sap/