Bình luận

• 

  kingofgame • 6:30 a.m. 29 Tháng 5, 2024 •

  include <bits/stdc++.h>

  using namespace std;
  typedef pair<int,int> pii;
  const int maxN = 105, maxM = 2605;
  const int INF = 0x3f3f3f3f;

  int N, rowTot, colTot, edgeID, p[maxN], cap[maxN][maxN];
  bool vis[maxM];
  vector<int> path, F[maxN];
  vector<pii> G[maxN];

  int bfs(int s = 0, int t = 2N+1){
  fill(p, p+2N+2, -1);
  p[s] = -2;

  queue<pii> Q;
  Q.push({s, INF});
  while(!Q.empty()){
      int u = Q.front().first;
      int f = Q.front().second;
      Q.pop();
  
      for(int v : F[u]){
          if(p[v] == -1 && cap[u][v]){
              p[v] = u;
              int aug = min(f, cap[u][v]);
              if(v == t)  return aug;
              Q.push({v, aug});
          }
      }
  }
  
  return 0;
  

  }

  void dfs(int u = 0){
  path.push_back(u);
  if(u == N) return;
  for(pii e : G[u]){
  int v = e.first;
  int id = e.second;
  if(cap[u][v] == 0 && !vis[id]){
  vis[id] = true;
  dfs(v);
  return;
  }
  }
  }

  int maxflow(int s = 0, int t = 2*N+1){
  int flow = 0, aug = 0;
  while(aug = bfs()){
  flow += aug;
  int u = t;
  while(u != s){
  int v = p[u];
  cap[v][u] -= aug;
  cap[u][v] += aug;
  u = v;
  }
  }
  return flow;
  }

  int main(){
  scanf("%d", &N);
  for(int i = 1, c; i <= N; i++){
  scanf("%d", &c);
  G[0].push_back({i, ++edgeID});
  F[0].push_back(i);
  F[i].push_back(0);
  cap[0][i] += c;
  rowTot += c;
  }
  for(int i = N+1, c; i <= 2N; i++){
  scanf("%d", &c);
  G[i].push_back({2N+1, ++edgeID});
  F[i].push_back(2N+1);
  F[2N+1].push_back(i);
  cap[i][2N+1] += c;
  colTot += c;
  }
  for(int i = 1; i <= N; i++){
  for(int j = N+1; j <= 2N; j++){
  G[i].push_back({j, ++edgeID});
  F[i].push_back(j);
  F[j].push_back(i);
  cap[i][j]++;
  }
  }

  int K = maxflow();
  if(rowTot != colTot || K != rowTot){
      printf("-1\n");
      return 0;
  }
  
  for(int i = 1; i <= N; i++){
      for(int j = 1; j <= N; j++)
          printf("%c", (cap[i][j+N] ? '.' : 'X'));
      printf("\n");
  }
  

  }

  -1

  Phản hồi Chia sẻ
• 

  vanphukhang_0604 • 8:49 p.m. 14 Tháng 8, 2023 • ← chỉnh sửa 4 →

  Grid Puzzle I - Câu đố trên lưới I

  Cho một lưới có kích thước \(n \times n\), nhiệm vụ của bạn là chọn một số ô từ mỗi hàng và mỗi cột. Bạn sẽ chọn như thế nào?

  Input

  • Dòng đầu tiên chứa số nguyên \(n \ (1 \leq n \leq 50)\): kích thước của lưới. Các hàng và cột được đánh số từ \(1, 2, \ldots, n\).
  • Dòng tiếp theo chứa \(n\) số nguyên \(a_1, a_2, \ldots, a_n \ (0 \leq a_i \leq n)\): Bạn phải chọn đúng \(a_i\) ô từ hàng thứ \(i\).
  • Dòng cuối cùng chứa \(n\) số nguyên \(b_1, b_2, \ldots, b_n \ (0 \leq b_j \leq n)\): Bạn phải chọn đúng \(b_j\) ô từ cột thứ \(j\).

  Output

  • In ra \(n\) dòng mô tả cách bạn chọn các ô trên lưới (in X nếu bạn chọn một ô hoặc . nếu bạn không chọn ô đó). Bạn có thể in ra bất kì cách chọn nào thoả mãn yêu cầu đề.

  • Nếu không có cách chọn nào thoả mãn, hãy in ra một số \(-1\) duy nhất.

  Example

  Test 1

  Input

  5
  0 1 3 2 0
  1 2 2 0 1

  Output

  .....
  ..X..
  .XX.X
  XX...
  .....

  0

  Phản hồi Chia sẻ