【ネットワークフロー】宇宙飛行計画

Description
W                      。                      。                E={E1，E2，…，Em}，                   I={I1， I2，…In}。  Ej        I   Rj ÍI。

    Ik    ck  。  Ej               pj  。W              ，                                        。                           

     。

              ，              。

Input
   1  2     m n。m    ，n    。    m  ，            。                 ；                  。     n            。

Output
  1      ； 2      ；        

Sample Input
2 3                      
10 1 2                
25 2 3                    
5 6 7

Sample Output
1 2
1 2 3
1 7

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <bitset>
using std::cin;
using std::bitset;

const char fi[] = "shut.in";
const char fo[] = "shut.out";
const int maxN = 110;
const int MAX = 0x3fffff00;
const int MIN = -MAX;

int map[maxN][maxN];
int f[maxN][maxN];
int d[maxN], cnt[maxN];
int t[maxN], ele[maxN][maxN];
bitset <maxN> expr, instr;
int N, M, n, ans, c;

  void init_file()
  {
    freopen(fi, "r", stdin);
    freopen(fo, "w", stdout);
    std::ios::sync_with_stdio(false);
  }

  void readdata()
  {
    cin >> M >> N;
    n = M + N + 2;
    for (int i = 2; i < M + 2; ++i)
    {
      cin >> c;
      ans += c;
      map[1][i] = f[1][i] = c;
      while (1)
      {
        if (cin.peek() == '
') break;
        cin >> c;
        ele[i - 1][++t[i - 1]] = c;
        map[i][c + M + 1] = f[i][c + M + 1] = MAX;
      }
    }
    for (int i = M + 2; i < n; ++i)
    {
      cin >> c;
      map[i][n] = f[i][n] = c;
    }
  }

  int Sap(int u, int Lim)
  {
    if (u == n) return Lim;
    int tmp = 0;
    for (int v = 1; v < n + 1; ++v)
     if (f[u][v] > 0 && d[u] == d[v] + 1)
      {
        int k = Sap(v, std::min(Lim
          - tmp, f[u][v]));
        if (k <= 0) continue;
        f[u][v] -= k;
        f[v][u] += k;
        if ((tmp += k) == Lim) return tmp;
      }
    if (d[1] >= n) return tmp;
    if ((--cnt[d[u]]) <= 0) d[1] = n;
    ++cnt[++d[u]];
    return tmp;
  }

  void work()
  {
    cnt[0] = n;
    while (d[1] < n) ans -= Sap(1, MAX);
    if (!ans) {printf("0"); return; }
    expr.set();
    instr.set();
    int k;
    for (k = 0; k < n; ++k)
      if (!cnt[k]) break;
	//    。
    for (int i = 2; i < n; ++i)
     if (d[i] < k)
      {
        if (i > M + 1) instr.reset(i - M - 1);
        else expr.reset(i - 1);
      }
	//           。
    for (int i = 1; i < M + 1; ++i)
      if (expr.test(i)) printf("%d ", i);
    printf("
");
    for (int i = 1; i < N + 1; ++i)
      if (instr.test(i)) printf("%d ", i);
    printf("
%d", ans);
  }

int main()
{
  init_file();
  readdata();
  work();
  exit(0);
}