1352.cpp

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

/*  This Code is Submitted by wywcgs for Problem 1352 on 2006-01-02 at 11:05:03 */ 
#include <cstdio>
#include <cstring>
#include <cassert>
#include <vector>
#include <list>
#include <queue>
using namespace std;

const int MAX = 128;

struct cmp {
	bool operator ()(const int i1, const int i2) const {
		return i1 > i2;
	}
};

int main()
{
	priority_queue<int, vector<int>, cmp> Q;
	vector<int> S;
	list<int> up[MAX];
	bool front[MAX][MAX];
	int n[MAX], m, d, i;
	int in[MAX];
	
	while(scanf("%d %d", &m, &d) != EOF && d != 0) {
		for(i = 0; i < m; i++) {
			scanf("%d", &n[i]);
			up[i].clear();
		}
		memset(in, 0, sizeof(in));
		memset(front, false, sizeof(front));
		bool can = true;
		for(i = 0; i < d; i++) {
			int a, b;
			scanf("%d %d", &a, &b);
			if(a != b && !front[a][b]) up[a].push_back(b), front[a][b] = true, in[b]++;
			else if(a == b && n[a] < 2) can = false;
		}
		if(can) {
			while(!Q.empty()) Q.pop();
			S.clear();
			bool put[MAX] = { false };
			for(i = 0; i < m; i++) {
				if(n[i] > 1 || (n[i] != 0 && in[i] == 0)) Q.push(i), put[i] = true;
			}
			while(!Q.empty()) {
				int p = Q.top(); Q.pop();
				put[p] = false;
				list<int>::iterator it;
				for(it = up[p].begin(); it != up[p].end(); it++) {
					if(--in[*it] == 0 && !put[*it]) Q.push(*it), put[*it] = true;
				}
				up[p].clear();
				S.push_back(p); n[p]--;
				if(n[p] > 1 || (n[p] > 0 && in[p] == 0)) Q.push(p), put[p] = true;
			}
			for(i = 0; i < m; i++) {
				if(n[i] != 0) { can = false; break; }
			}
		}
		if(!can) printf("Impossible!\n");
		else {
			vector<int>::iterator it;
			for(it = S.begin(); it != S.end(); it++) {
				if(it != S.begin()) putchar(' ');
				printf("%d", *it);
			}
			putchar('\n');
		}
	}
	
	return 0;
}