2787 흔한 수열 문제

2787 흔한 수열 문제 https://www.acmicpc.net/problem/2787

숨겨진 수열 A가 있다.

• 1 x y v - x번째 수부터, y번째 수 중 제일 큰 값은 v
• 2 x y v - x번째 수부터, y번째 수 중 제일 작은 값은 v

위와 같은 query에 대한 답이 주어져있을 때 역으로 수열 A를 구하는 문제이다.

범위값을 조정하면서 풀려고했으나 도저히 감이 잡히지 않아서 문제 분류를 봤는데
flow문제였다.

[x, y] 까지 제일 큰 값이 v였다면 [x, y]를 [1, v]까지 연결해주는 형식이다.
하지만 잘못된 query도 주어지므로 query에 대해 연결되면 안되는 부분들을 체크해주고
query가 끝나면 그 외의 범위들에 대해 정점연결을 해주면 된다.
그 후 이분매칭을 시켜주면 된다.

나중에 다시풀어봐야겠다.

#include <cstdio> #include <vector> #include <queue> #include <algorithm> using namespace std; int N, M; vector<vector<int>> adj; int C[444][444], f[444][444]; bool check[222][222]; void add_edge(int u, int v, int c) {     adj[u].push_back(v);     adj[v].push_back(u);     C[u][v] = c; } int max_flow(int S, int E) {     int ret = 0;     while (1) {         vector<int> par(2 * N + 5, -1);         queue<int> q;         q.push(S);         while (!q.empty()) {             int here = q.front();             q.pop();             for (int next : adj[here]) {                 if (C[here][next] - f[here][next] > 0 && par[next] == -1) {                     par[next] = here;                     q.push(next);                 }             }         }         if (par[E] == -1) break;         ret++;         for (int i = E;i != S;i = par[i])             f[par[i]][i]++, f[i][par[i]]--;     }     return ret; } int main() {     scanf("%d%d", &N, &M);     for (int m = 0;m < M;m++) {         int f, l, r, v;         scanf("%d%d%d%d", &f, &l, &r, &v);         if (f == 1) {             for (int n = l;n <= r;n++)                 for (int k = v + 1;k <= N;k++) check[n][k] = true;         }         else if (f == 2) {             for (int n = l;n <= r;n++)                 for (int k = 1;k < v;k++) check[n][k] = true;         }         for (int n = 1;n < l;n++) check[n][v] = true;         for (int n = r + 1;n <= N;n++) check[n][v] = true;     }       adj = vector<vector<int>>(2 * N + 5, vector<int>());     int src = 0, sink = 2 * N + 4;     for (int n = 1;n <= N;n++) {         for (int m = 1;m <= N;m++) {             if (!check[n][m])                 add_edge(2 * n - 1, 2 * m, 1);         }         add_edge(src, 2 * n - 1, 1);         add_edge(2 * n, sink, 1);     }     if (max_flow(src, sink) == N) {         for (int n = 1;n <= N;n++) {             for (int m = 1;m <= N;m++)                 if (f[2 * n - 1][2 * m] >= 1) {                     printf("%d ", m);                     break;                 }         }         printf("\n");     }     else printf("-1\n");     return 0; } Colored by Color Scripter

cs