【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; }