【BZOJ 5335】【TJOI 2018】クイズ
【タイトルリンク】クリックしてリンク を開く
【考え方のポイント】の2分の1の答えを、上下境界のある最小ストリームで検証します. 時間複雑度(O(LogM*Dinic(M,sumK_i)).
【コード】
【考え方のポイント】
【コード】
#include
using namespace std;
const int MAXN = 505;
const int MAXP = 2005;
const int INF = 1e9;
template void chkmax(T &x, T y) {x = max(x, y); }
template void chkmin(T &x, T y) {x = min(x, y); }
template void read(T &x) {
x = 0; int f = 1;
char c = getchar();
for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
x *= f;
}
template void write(T x) {
if (x < 0) x = -x, putchar('-');
if (x > 9) write(x / 10);
putchar(x % 10 + '0');
}
template void writeln(T x) {
write(x);
puts("");
}
struct edge {int dest; int flow; unsigned home; };
int s, t, olds, oldt, tot, dist[MAXP];
vector a[MAXP];
unsigned curr[MAXP];
int dinic(int pos, int limit) {
if (pos == t) return limit;
int used = 0, tmp;
for (unsigned &i = curr[pos]; i < a[pos].size(); i++)
if (a[pos][i].flow != 0 && dist[pos] + 1 == dist[a[pos][i].dest] && (tmp = dinic(a[pos][i].dest, min(limit - used, a[pos][i].flow))) != 0) {
used += tmp;
a[pos][i].flow -= tmp;
a[a[pos][i].dest][a[pos][i].home].flow += tmp;
if (used == limit) return used;
}
return used;
}
bool bfs() {
static int q[MAXP], l = 0, r = -1;
for (int i = 0; i <= r; i++)
dist[q[i]] = 0;
q[l = r = 0] = s, dist[s] = 1;
while (l <= r) {
int tmp = q[l++];
for (unsigned i = 0; i < a[tmp].size(); i++)
if (a[tmp][i].flow != 0 && dist[a[tmp][i].dest] == 0) {
q[++r] = a[tmp][i].dest;
dist[a[tmp][i].dest] = dist[tmp] + 1;
}
}
return dist[t] != 0;
}
void addedge(int s, int t, int flow) {
a[s].push_back((edge) {t, flow, a[t].size()});
a[t].push_back((edge) {s, 0, a[s].size() - 1});
}
vector e[MAXN];
int limit, n, val[MAXN], pos[MAXN];
int inp[MAXN], outp[MAXN];
bool cmp(int x, int y) {
return val[x] < val[y];
}
bool check(int mid) {
tot = 0;
olds = ++tot; a[tot].clear();
oldt = ++tot; a[tot].clear();
s = ++tot; a[tot].clear();
t = ++tot; a[tot].clear();
for (int i = 1; i <= n; i++) {
int tmp = pos[i];
inp[tmp] = ++tot; a[tot].clear();
outp[tmp] = ++tot; a[tot].clear();
addedge(olds, inp[tmp], INF);
addedge(outp[tmp], oldt, INF);
addedge(inp[tmp], outp[tmp], INF);
if (i <= mid) {
addedge(s, outp[tmp], 1);
addedge(inp[tmp], t, 1);
}
}
for (int i = 1; i <= n; i++) {
int tmp = pos[i];
for (unsigned j = 0; j < e[tmp].size(); j++)
addedge(outp[tmp], inp[e[tmp][j]], INF);
}
int tmp = 0;
while (bfs()) {
memset(curr, 0, sizeof(curr));
tmp += dinic(s, INF);
}
addedge(oldt, olds, INF);
int ans = 0;
while (bfs()) {
memset(curr, 0, sizeof(curr));
ans += dinic(s, INF);
}
return ans <= limit + 1;
}
int main() {
read(limit), read(n);
for (int i = 1; i <= n; i++) {
read(val[i]);
pos[i] = i;
int k; read(k);
while (k--) {
int x; read(x);
e[i].push_back(x);
}
}
sort(pos + 1, pos + n + 1, cmp);
int l = 1, r = n;
while (l < r) {
int mid = (l + r + 1) / 2;
if (check(mid)) l = mid;
else r = mid - 1;
}
if (l == n) printf("AK
");
else printf("%d
", val[l + 1]);
return 0;
}