2172.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 2172 on 2006-03-15 at 22:31:39 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX = 400;

int et[MAX], order[MAX], n, m;
bool vst[MAX], ev[MAX][MAX];

bool find(int);

int main()
{
	int i, j;

	while(scanf("%d %d", &n, &m) != EOF) {
		memset(et, 0, sizeof(et)); memset(vst, false, sizeof(vst));
		for(i = 0; i < n; i++)
			for(j = 0; j < m; j++) {
				int a; scanf("%1d", &a);
				ev[i][j] = (a == 1);
				if(ev[i][j] && j != 0) et[i]++;
			}
		order[0] = 0; vst[0] = true; find(1);
		for(i = 0; i < m; i++) printf("%d\n", order[i]);
	}
	
	return 0;
}

bool find(int o)
{
	if(o == m) return true;
	int i, j;
	for(i = 1; i < m; i++) {
		if(vst[i]) continue;
		bool can = true;
		for(j = 0; j < n && can; j++)
			if(ev[j][order[o-1]] && et[j] != 0 && !ev[j][i]) can = false;
		if(!can) continue;
		for(j = 0; j < n; j++) if(ev[j][i]) et[j]--;
		order[o] = i; vst[i] = true;
		if(find(o+1)) return true;
		for(j = 0; j < n; j++) if(ev[j][i]) et[j]++;
		vst[i] = false;
	}
	return false;
}