题目描述
就在土匀匀还在准备联赛的时候，学霸
已经拿到了金牌。于是，开心的学霸用他的笔记本玩起了足球联盟。
足球联盟里有 (n) 只球队，编号为 (1)~(n)，的球队编号为 (n)。现在联赛已经进行了很多轮，每个球队都有了一定的积分。
聪明的通过对游戏源代码的分析，得到了接下来的所有赛程。
想，如果他可以控制所有剩下比赛的结果的话，能否使得他的球队获得比其他所有球队都更高的分数。
积分的规则是：对于一场比赛，赢的球队得 (2) 分，输的球队得 (0) 分，如果是平局，两支球队各得 (1) 分。
输入格式
第一行为一个整数 (T)，表示数据组数。对于每组数据：
第一行为两个正整数 (n) 和 (m)，表示球队的数目和剩余比赛的数目。
第二行为 (n) 个非负整数，表示每个球队现在的积分，不超过 (1000)。
接下来 (m) 行，每行两个整数 (x)、(y)，表示球队 (x) 和球队 (y) 之间有一场比赛。
输出格式
每组数据一行，如果能使自己的球队获得最高的分数（没有并列），输出 YES，否则输出 NO。
数据范围
测试时间限制 (1000 mathrm{ms})，空间限制 (256 mathrm{MiB})。
- 对于 (30\%) 的数据，(1le nle 10)，(1le mle 10)；
- 对于 (60\%) 的数据，(1le nle 30)，(1le mle 100)；
- 对于 (100\%) 的数据，(1le nle 100)，(1le mle 1000)，(1le Tle 10)，(1le x_i,y_ile n)，(x_i eq y_i)。
分析
这道题是一道很有意思的题。要根据题中的限制来选择算法。
我们就假设那个人是 A 君。
(30 mathtt{pts})
枚举每一种比赛的胜负情况，再暴力算出来。
复杂度：(Theta(3^mn))。
(60 mathtt{pts}) && (100 mathtt{pts})
我们有必要想一下，有什么结论可以使用。
如果有比赛是 A 君的球队参加的，这场比赛 A 君的球队必须赢
这是显然的，这样可以尽可能让 A 君的球队得分。
其他球队不能赢太多分
这也是显然的，因为赢的分数太多了就可能导致 A 君的球队落选。
但是，对于剩下的球队，我们难以指控。我们应该抽象一下这道题。
首先，有若干个数，每个数都有一个初始值。
接下来，我们有若干个操作，可以将其中两个数分别加上 (a,b)，要求 (a,bin mathbb{N}) 且 (a+b=2)
最后，我们要知道，是否存在一种操作，使完成所有操作后每个数都小于一个给定的数。
当然，如果我们换一种表述，你就有可能发现这道题的正解：
有若干个水罐，每一个水罐都有一个固定容积，初始时为空。我们有若干个倒水措施，使得其中两个水罐里加起来能够倒入 (2) 单位的水。
最后，我们想要知道，是否存在一个倒水操作，使得所有的水罐都不会溢出。
没错，我们可以利用网络流来解决这个问题。
图可以这样设计：
- 有一个超级源点，用来倒出水。
- 对于每一个倒出操作，固定一个节点，从源点到这个节点连一条流量为 (2) 的弧。
- 接下来，从每一个操作节点向两个倒入的水罐分别连一条流量为无穷大的弧。
- 最后，对于每一个水罐节点，都向超级汇点连一条权值为自身容积的边。
画出来就是这个样子：
对应到这题上来，每一个球队的“容量”实际上就是能赢多少分，却不会超过 A 君的球队。
就是 A 君球队的分数减去对应球队分数再减一。
如果最后跑出来的最大流已经是 S 的满流，那么就是可以出线的。反之同理。
这样，图的复杂度是 (Theta(n+m))，再跑一遍网络流，复杂度就是 (mathcal{O}((n+m)^3))，基本跑不满，可以通过本题。
（这里的复杂度是以基本 ISAP 计算，如果用 HLPP 或者 LCT 优化 ISAP 还能更快。）
Code
又是又臭又长的代码，但是核心还是很短的。
#include <queue>
#include <cstdio>
#include <cctype>
#include <cstring>
using namespace std;
const int max_n = 100, max_m = 1000, max_node = max_n + max_m + 1, max_edge = max_m * 3 + max_n, INF = 0x3f3f3f3f;
int hd[max_node], des[max_edge<<1], val[max_edge<<1], occ[max_edge<<1], nxt[max_edge<<1], edge_cnt = 0;
int hei[max_node], gap[max_node], cur[max_node], sco[max_n];
bool flag;
queue<int> q;
inline int nid(int id) { return max_m + 1 + id; }
inline int my_min(int a, int b) { return (a < b)? a:b; }
inline int read()
{
int ch = getchar(), n = 0, t = 1;
while (isspace(ch)) { ch = getchar(); }
if (ch == '-') { t = -1, ch = getchar(); }
while (isdigit(ch)) { n = n * 10 + ch - '0', ch = getchar(); }
return n * t;
}
void _a(int s, int t, int v)
{
des[edge_cnt] = t, val[edge_cnt] = v;
nxt[edge_cnt] = hd[s], hd[s] = edge_cnt++;
}
void add_edge(int s, int t, int v)
{
_a(s, t, v);
_a(t, s, 0);
}
int aug(int s, int t, int lim)
{
if (s == t)
return lim;
if (!flag)
return 0;
int tmp, flow = 0;
for (int& p = cur[s]; p != -1; p = nxt[p])
if (hei[des[p]] == hei[s] - 1)
{
tmp = aug(des[p], t, my_min(lim, val[p] - occ[p]));
flow += tmp, occ[p] += tmp, occ[p^1] -= tmp, lim -= tmp;
if (lim <= 0)
return flow;
}
gap[hei[s]]--, cur[s] = hd[s];
if (!gap[hei[s]])
flag = false;
hei[s]++, gap[hei[s]]++;
return flow;
}
int main()
{
int cas = read(), n, m, ta, tb, rcnt;
bool over;
while (cas--)
{
memset(hd, -1, sizeof(hd));
memset(hei, -1, sizeof(hei));
memset(gap, 0, sizeof(gap));
memset(occ, 0, sizeof(occ));
edge_cnt = 0, over = false, flag = true, rcnt = 0;
n = read(), m = read();
for (int i = 0; i < n; i++)
sco[i] = read();
for (int i = 0; i < m; i++)
{
ta = read() - 1, tb = read() - 1;
if (ta == n - 1 || tb == n - 1)
sco[n-1] += 2;
else
{
rcnt++;
add_edge(0, rcnt, 2);
add_edge(rcnt, nid(ta), INF);
add_edge(rcnt, nid(tb), INF);
}
}
for (int i = 0; i < n - 1; i++)
{
if (sco[n-1] - sco[i] - 1 < 0)
{
puts("NO");
over = true;
break;
}
add_edge(nid(i), max_node - 1, sco[n-1] - sco[i] - 1);
}
if (over)
continue;
for (int i = 0; i < max_node; i++)
cur[i] = hd[i];
hei[max_node-1] = 0, gap[0] = 1;
q.push(max_node - 1);
while (!q.empty())
{
ta = q.front();
q.pop();
for (int p = hd[ta]; p != -1; p = nxt[p])
if (hei[des[p]] == -1)
{
hei[des[p]] = hei[ta] + 1;
gap[hei[des[p]]]++;
q.push(des[p]);
}
}
ta = 0;
while (flag)
ta += aug(0, max_node - 1, INF);
if (ta == rcnt * 2)
puts("YES");
else
puts("NO");
}
return 0;
}
后记
当时考场上做这道题时，第一感觉居然是 DP。后来才发现是网络流。
看来，这类图论建模的题还要多多练习啊……