1494.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/*  This Code is Submitted by wywcgs for Problem 1494 on 2005-11-06 at 19:21:11 */ 
#include <cstdio>
#include <cstring>

const int MAX = 128;

bool edge[MAX][MAX];
bool hinge[MAX];
int n;

void Dijkstra(int);

int main()
{
	int p, m;
	int i, j;
	
	while(scanf("%d", &n) == 1) {
		if(n == 0) {
			return 0;
		} else {
			for(i = 0; i < n; i++) {
				for(j = 0; j < n; j++) {
					scanf("%1d", &p);
					if(p == 0) {
						edge[i][j] = false;
					} else {
						edge[i][j] = true;
					}
				}
			}
			memset(hinge, false, sizeof(hinge));
			for(i = 0; i < n; i++) {
				Dijkstra(i);
			}
			m = 0;
			for(i = 0; i < n; i++) {
				if(hinge[i]) {
					m++;
				}
			}
			printf("%d\n", m);
		}
	}
	
	return 0;
}

void Dijkstra(int p)
{
	int prev[MAX], d[MAX], pn[MAX] = {0};
	int i, j, min, mini;
	bool visit[MAX] = {false};
	
	for(i = 0; i < n; i++) {
		d[i] = MAX;
	}
	d[p] = 0;
	pn[p] = 1;
	prev[p] = p;
	for(i = 0; i < n; i++) {
		min = MAX;
		mini = -1;
		for(j = 0; j < n; j++) {
			if(!visit[j] && d[j] < min) {
				min = d[j];
				mini = j;
			}
		}
		if(mini == -1) {
			break;
		} else {
			visit[mini] = true;
			for(j = 0; j < n; j++) {
				if(!visit[j] && edge[mini][j]) {
					if(d[j] > d[mini] + 1) {
						d[j] = d[mini] + 1;
						pn[j] = pn[mini];
						prev[j] = mini;
					} else if(d[j] == d[mini] + 1) {
						pn[j] += pn[mini];
					}
				}
			}
		}
	}
	for(i = 0; i < n; i++) {
		if(pn[i] == 1) {
			for(j = prev[i]; j != p; j = prev[j]) {
				hinge[j] = true;
			}
		}
	}
}