UVA 10092 - The Problem with the Problem Setter

  1  /*
  2  Problem link
  3  Type: Graph - Maximum Flow
  4  Algorithm:
  5      Build a residual graph with a source and sink.
  6      Between the source and the sink are categories and problems
  7  
  8      The capacity from the source to the categories equal to the
  9      the number of problem in that category.
 10  
 11      The capacity from one category to one problem is equal to 1
 12      if that problem can be grouped in the category or 0 otherwise.
 13  
 14      The capacity from each problem to the sink is equal to 1.
 15  
 16      Find the maximum flow from the graph, if the maximum flow equal
 17      to the sum of all the problem from each category then the test can
 18      be made.
 19  */
 20  #include <iostream>
 21  #include <cstdio>
 22  #include <cstring>
 23  #include <cmath>
 24  #include <cstdlib>
 25  #include <vector>
 26  #include <queue>
 27  
 28  using namespace std;
 29  const char* fi = "10092.inp";
 30  const char* fo = "10092.out";
 31  const int maxn = 1500;
 32  const int oo = 1000000;
 33  
 34  vector<int> p;
 35  queue<int> q;
 36  int a[maxn][maxn];
 37  int f,n,np,s,t,nn,sump;
 38  
 39  bool readFile();
 40  int findMaxFlow();
 41  
 42  int main() {
 43      freopen(fi,"r",stdin);
 44      freopen(fo,"w",stdout);
 45  
 46      while (readFile()) {
 47          int result = findMaxFlow();
 48          if (result == sump) {
 49              cout << 1 << endl;
 50              for (int i = 1; i <= n; i++) {
 51                  int cnt = 0;
 52                  for (int j = 1; j <= np; j++) {
 53                      if (a[j+n][i] == 1) {
 54                          cnt++;
 55                          if (cnt > 1) cout << " " << j;
 56                          else cout << j;
 57                      }
 58                  }
 59                  cout << endl;
 60              }
 61          } else cout << 0 << endl;
 62      }
 63      return 0;
 64  }
 65  
 66  bool readFile() {
 67      cin >> n >> np;
 68      if (n == 0 && np == 0) return false;
 69  
 70      nn = n+np+1; sump = 0;
 71      for (int i = 0; i <= nn; i++)
 72          for (int j = 0; j <= nn; j++) a[i][j] = 0;
 73  
 74      int k;
 75      s = 0; t = n+np+1;
 76      for (int i = 1; i <= n; i++) {
 77          cin >> a[s][i];
 78          sump += a[s][i];
 79      }
 80  
 81      for (int i = 1; i <= np; i++) {
 82          cin >> k;
 83          for (int j = 1; j <= k; j++) {
 84              int value;
 85              cin >> value;
 86              a[value][i+n] = 1;
 87          }
 88          a[i+n][t] = 1;
 89      }
 90      return true;
 91  }
 92  
 93  void augment(int v, int minEdge) {
 94      if (v == s) { f = minEdge; return; }
 95      else if (p[v] != -1) {
 96          augment(p[v], min(minEdge, a[p[v]][v]));
 97          a[p[v]][v] -= f;
 98          a[v][p[v]] += f;
 99      }
100  }
101  
102  int findMaxFlow() {
103      int result = 0;
104      while (true) {
105          p.assign(nn+1, -1);
106          f = 0;
107          while (!q.empty()) q.pop();
108  
109          q.push(s);
110          while (!q.empty()) {
111              int u = q.front(); q.pop();
112  
113              if (u == t) break;
114              for (int v = 0; v <= nn; v++) {
115                  if (a[u][v] > 0 && p[v] == -1)
116                      q.push(v), p[v] = u;
117              }
118          }
119  
120          augment(t, +oo);
121          if (f == 0) break;
122          result += f;
123      }
124      return result;
125  }