kleague.cpp

PASCAL光盘资料PASCAL光盘资料PASCAL光盘资料

#include <fstream>
#include <iostream>
#include <string.h>

using namespace std;

ifstream fin("kleague.in");
ofstream fout("kleague.out");
#define cout fout

const int MAXN = 50, MAX = MAXN * MAXN + MAXN + 50;

int n, w[MAXN], wm[MAXN], a[MAXN][MAXN];
int g[MAX][MAX], c[MAX][MAX], f[MAX][MAX];

void addedge(int x, int y, int cc) {
  c[x][y] = cc, f[x][y] = 0;
  g[x][++g[x][0]] = y, g[y][++g[y][0]] = x;
}

int min(int a, int b) {
  return a < b ? a : b;
}

int judge(int);
void maxflow(int, int);

main() {
  int T;
  for (fin >> T; T--;) {
    int i, j;

    fin >> n;
    for (i = 1; i <= n; i++) {
      fin >> w[i] >> j;
      wm[i] = w[i];
    }

    for (i = 1; i <= n; i++)
      for (j = 1; j <= n; j++) {
	fin >> a[i][j];
	wm[i] += a[i][j];
      }

    for (i = j = 1; i <= n; i++)
      if (judge(i)) {
	if (j) j = 0; else cout << ' ';
	cout << i;
      }
    cout << endl;
  }

  return 0;
}


int judge(int id) {
  int i, j;
  for (i = 0; i < MAX; i++)
    g[i][0] = 0;
  
  for (i = 1; i <= n; i++)
    if (wm[id] < w[i]) return 0;
    else addedge(i, n * n + n + 1, wm[id] - w[i]);

  for (i = 1; i <= n; i++)
    for (j = i + 1; j <= n; j++)
      if (a[i][j]) {
	addedge(0, i * n + j, a[i][j]);
	addedge(i * n + j, i, a[i][j]);
	addedge(i * n + j, j, a[i][j]);
      }

  maxflow(0, n * n + n + 1);

  int ok = 1;
  for (i = 1; ok && i <= n; i++)
    for (j = i + 1; ok && j <= n; j++)
      if (a[i][j] && f[0][i * n + j] < a[i][j])
	ok = 0;

  return ok;
}


int delta[MAX], mark[MAX], from[MAX], queue[MAX];

void maxflow(int s, int t) {
  for (;;) {
    memset(delta, 0, sizeof(int) * (n * n + n + 2)); delta[s] = 2147483647;
    memset(mark, 0, sizeof(int) * (n * n + n + 2)); mark[s] = 1;
    queue[queue[0] = 1] = s;

    int i, j, x, y;
    for (i = 1; i <= queue[0]; i++)
      for (x = queue[i], j = 1; j <= g[x][0]; j++) if (!mark[y = g[x][j]])
	if (f[x][y] < c[x][y])
	  mark[y] = 1, from[y] = x, queue[++queue[0]] = y, delta[y] = min(delta[x], c[x][y] - f[x][y]);
	else if (f[y][x])
	  mark[y] = 1, from[y] = -x - 1, queue[++queue[0]] = y, delta[y] = min(delta[x], f[y][x]);

    if (!delta[t]) break;

    for (i = t; i != s; i = j) {
      j = from[i];
      if (j >= 0) f[j][i] += delta[t];
      else f[i][j = -j - 1] -= delta[t];
    }
  }
}