传送门考场上的思路失误卡常参考代码
传送门
考场上的思路
很明显需要二分图。发现第一问可以一个一个贪心处理，每次动态加边跑网络流。
第二问的话，发现可以利用第一问的答案，对于一个人
i
i
，他之前的所有人的档次一定是第一问的答案。所以可以枚举答案，对于前面的人只加上他第一问的答案对应的边，这也正好说明了为什么对 cc 有限制。
本来以为稳了，不说
100
100
，至少
80
80
分还是有的，于是我就期望得分
100
100
，结果一下来，
40
40
什么鬼？？！
失误
这里详细说一下第二问我是怎么做的。对于第
i
i
个人，我先把他档次小于等于 sisi 的边加入到图中，然后跑最大流。如果没有流，说明这个人没有理想，答案为
i
i
，否则我们从 11 开始枚举到
i−1
i
−
1
。
对于枚举到的人
j
j
，把他的档次为他第一问的答案的边加进图中跑最大流，如果能够增广，说明从 11 到
i
i
增广也能增广；如果不能增广，说明从 11 到
i
i
增广也不能增广（即：存在矛盾）。这时我就退出。
问题就出在上面这里。我忘记了如果第一问答案为 m 1m 1 要直接跳过……
卡常
结果还是被卡成了
90
90
分。
可能我的时间复杂度不对吧，但我感觉挺对的……仔细观察，发现根本不需要 Dinic，因为一次最多只能找到一条增广路，干嘛要打多路增广呢？直接 Edmonds-Karp 单路增广就好了。在氧气的环绕下，发现 Dinic 并不比 Edmonds-Karp 慢，换成了 EK 还是超时。
然后我把队列换成手写的了，然后就卡过了……
另外中途我尝试把 vector 换成数组，结果慢了一倍。得出结论：当开 O2 优化时，vector 很快，不开 O2 优化时 vector 很慢，数组稍微好一点。queue 由于其实现的问题，常数很大，建议手写（毕竟 BFS 时元素总量是确定的）。
参考代码
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <cassert>
#include <cctype>
#include <climits>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <list>
#include <functional>
typedef long long LL;
typedef unsigned long long ULL;
using std::
cin;
using std::
cout;
using std::endl;
typedef int INT_PUT;
INT_PUT readIn()
{
INT_PUT a =
0;
bool positive =
true;
char ch = getchar();
while (!(ch ==
'-' ||
std::
isdigit(ch))) ch = getchar();
if (ch ==
'-')
{
positive =
false;
ch = getchar();
}
while (
std::
isdigit(ch))
{
(a *=
10) -= ch -
'0';
ch = getchar();
}
return positive ? -a : a;
}
void printOut(INT_PUT x)
{
char buffer[
20];
int length =
0;
if (x <
0)
putchar(
'-');
else x = -x;
do buffer[length++] = -(x %
10) +
'0';
while (x /=
10);
do putchar(buffer[--length]);
while (length);
putchar(
' ');
}
const int INF = (~(
int(
1) << (
sizeof(
int) *
8 -
1))) >>
1;
const int maxn =
205;
int T, C;
int n, m;
int b[maxn];
int rect[maxn][maxn];
std::
vector<std::vector<int> > teacher[maxn];
int s[maxn];
struct NetworkFlow
{
struct Edge
{
int from, to, cap, flow;
Edge() {}
Edge(
int from,
int to,
int cap) : from(from), to(to), cap(cap), flow() {}
};
std::
vector<Edge> edges;
std::
vector<std::vector<int> > G;
int s, t;
void addEdge(
int from,
int to,
int cap)
{
edges.push_back(Edge(from, to, cap));
edges.push_back(Edge(to, from,
0));
int i = edges.size();
G[from].push_back(i -
2);
G[to].push_back(i -
1);
}
std::
vector<int> vis;
std::
vector<int> opt;
std::
vector<int> pre;
bool BFS(
int& flow)
{
static int stamp;
stamp++;
static int q[maxn *
2];
int head =
0, tail =
0;
q[tail++] = s;
vis[s] = stamp;
opt.clear();
opt.resize(n + m +
2,
0);
pre.resize(n + m +
2);
opt[s] = INF;
while (head != tail)
{
int from = q[head++];
for (
int i =
0; i < G[from].size(); i++)
{
const Edge& e = edges[G[from][i]];
if (e.flow < e.cap && vis[e.to] != stamp)
{
opt[e.to] =
std::min(opt[from], e.cap - e.flow);
pre[e.to] = G[from][i];
vis[e.to] = stamp;
q[tail++] = e.to;
if (vis[t] == stamp)
break;
}
}
}
if (vis[t] != stamp)
return false;
flow += opt[t];
for (
int u = t; u != s; u = edges[pre[u]].from)
{
edges[pre[u]].flow += opt[t];
edges[pre[u] ^
1].flow -= opt[t];
}
return true;
}
int EdmondsKarp()
{
int flow =
0;
while (BFS(flow));
return flow;
}
void clear(
int newSize)
{
edges.clear();
edges.reserve(n * m *
10);
G.clear();
G.resize(newSize);
vis.resize(newSize);
}
} nf;
#define RunInstance(x) delete new x
struct cheat
{
cheat()
{
int lastSel =
0;
int remain = b[
1];
for (
int i =
1; i <= n; i++)
if (rect[i][
1] ==
1)
{
if (remain)
{
printOut(
1);
lastSel = i;
remain--;
}
else
printOut(m +
1);
}
else
printOut(m +
1);
putchar(
'\n');
for (
int i =
1; i <= n; i++)
if (rect[i][
1] ==
1)
printOut(
std::max(
0, i - lastSel));
else
printOut(i);
}
};
struct work
{
int ans1[maxn];
int ans2[maxn];
work() : ans1(), ans2()
{
nf.clear(n + m +
2);
nf.s =
0;
nf.t = n + m +
1;
for (
int i =
1; i <= n; i++)
nf.addEdge(nf.s, i,
1);
for (
int i =
1; i <= m; i++)
nf.addEdge(n + i, nf.t, b[i]);
for (
int i =
1; i <= n; i++)
{
int& j = ans1[i];
for (j =
1; j <= m; j++)
{
for (
int k =
0; k < teacher[i][j].size(); k++)
nf.addEdge(i, n + teacher[i][j][k],
1);
if (nf.EdmondsKarp())
break;
}
}
for (
int i =
1; i <= n; i++)
{
if (ans1[i] <= s[i])
{
ans2[i] =
0;
continue;
}
nf.clear(n + m +
2);
for (
int j =
1; j <= n; j++)
nf.addEdge(nf.s, j,
1);
for (
int j =
1; j <= m; j++)
nf.addEdge(n + j, nf.t, b[j]);
for (
int j =
1; j <= s[i]; j++)
for (
int k =
0; k < teacher[i][j].size(); k++)
nf.addEdge(i, n + teacher[i][j][k],
1);
if (!nf.EdmondsKarp())
{
ans2[i] = i;
continue;
}
int& j = ans2[i];
for (j =
1; j < i; j++)
{
if (ans1[j] == m +
1)
continue;
const std::
vector<int> Teacher = teacher[j][ans1[j]];
for (
int k =
0; k < Teacher.size(); k++)
nf.addEdge(j, n + Teacher[k],
1);
int aug = nf.EdmondsKarp();
if (!aug)
break;
}
j = i - j;
}
for (
int i =
1; i <= n; i++)
printOut(ans1[i]);
putchar(
'\n');
for (
int i =
1; i <= n; i++)
printOut(ans2[i]);
}
};
void run()
{
T = readIn();
C = readIn();
while (T--)
{
n = readIn();
m = readIn();
for (
int i =
1; i <= m; i++)
b[i] = readIn();
for (
int i =
1; i <= n; i++)
{
teacher[i].clear();
teacher[i].resize(m +
1);
for (
int j =
1; j <= m; j++)
if (rect[i][j] = readIn())
teacher[i][rect[i][j]].push_back(j);
}
for (
int i =
1; i <= n; i++)
s[i] = readIn();
if (m ==
1)
RunInstance(cheat);
else
RunInstance(work);
putchar(
'\n');
}
}
int main()
{
#ifndef LOCAL
freopen(
"mentor.in",
"r", stdin);
freopen(
"mentor.out",
"w", stdout);
#endif
run();
return 0;
}
