Untitled

 avatar
unknown
plain_text
4 years ago
3.5 kB
5
Indexable
#include<stdio.h>
#define MAX_Vertices 20
#define MAX_Length 20
#define MAX_Element 40
#define infinity 999999
typedef struct{
	int A[MAX_Vertices][MAX_Vertices];
	int n;
}Graph;
void init_Graph(Graph *G, int n){
	G->n=n;
	int i, j;
	for(i=1; i<=G->n; i++)
		for(j=1; j<=G->n; j++)
			G->A[i][j] = 0;
}
void print_Graph(Graph G){
	int i, j;
	for(i=1; i<=G.n; i++){
		for(j=1; j<=G.n; j++)
			printf("%d ", G.A[i][j]);
		printf("\n");
    } 
    printf("\n");
}
void add_edge(Graph *G, int x, int y){
	G->A[x][y] =1;
	//G->A[y][x] =1;
}
int adjacent(Graph *G, int x, int y){
	return(G->A[x][y] !=0 );
}
int degree(Graph *G, int x){
	int i, deg=0;
	for(i=1; i<=G->n; i++){
		if(adjacent(G, x, i)) deg++;
	}
	return deg;
}
typedef struct{
	int data[MAX_Length];
	int size;
}List;
void make_null(List *list){
	list->size=0;
}
void push_back(List *list, int x){
	list->data[list->size] =x;
	list->size++;
}
int element_at(List *list, int i){
	return list->data[i-1];
}
void copy_list(List *l1, List *l2){
	int i;
	make_null(l1);
	for(i=1; i<=l2->size; i++){	
		push_back(l1, element_at(l2, i));
//		int t = element_at(l2, i);
//		l1->data[i-1] = t;
	}			
}
List neighbors(Graph *G, int x){
	int i;
	List list;
	make_null(&list);
	for(i=1; i<=G->n; i++)
		if(adjacent(G, x, i)) push_back(&list, i);
	return list;
}
typedef struct {
	int data[MAX_Element];
	int front, rear;
}Queue;

void make_null_queue(Queue *Q){
	Q->front =0;
	Q->rear =-1;
}

int empty(Queue *Q){
	return Q->front > Q->rear;
}

void push(Queue *Q, int x){
	Q->rear++;
	Q->data[Q->rear] =x;
}

int top(Queue *Q){
	return Q->data[Q->front];
}

void pop(Queue *Q){
	Q->front++;
}

void topo_sort(Graph *G, List *L){
	int d[MAX_Vertices];
	int u,x, i;
	Queue Q;
	make_null_queue(&Q);
	
	for (u = 1; u <= G->n; u++)
		d[u] = 0;
	for (x = 1; x <= G->n; x++)
		for (u = 1; u <= G->n; u++)
			if (G->A[x][u] != 0)
				d[u]++;
				
	for(u=1; u<=G->n; u++)
		if(d[u] == 0)
			push(&Q, u);
	make_null(L);
	while(!empty(&Q)){
		int u = top(&Q); pop(&Q);
		push_back(L, u);
		List list = neighbors(G, u);
		for(i=1; i<=list.size; i++){
			int v = element_at(&list, i);
			d[v]--;
			if(d[v] == 0)
				push(&Q, v);
		}
	}
}
int min(int x, int y){
	return (x<y)?x:y;
}
int max(int x, int y){
	return (x>y)?x:y;
}
int main(){
	Graph G;
	int n, u, x, v, j;
	int d[100];
//	freopen("dothi.txt", "r", stdin);
	scanf("%d", &n);
	init_Graph(&G, n+2);
	d[n+1] =0;
	for(u=1; u<=n; u++){
		scanf("%d", &d[u]);
		do{
			scanf ("%d", &x);
			if(x>0) add_edge(&G, x, u);
		}while(x>0);
	}
		
	for(u=1; u<=n; u++){
		int deg_neg = 0;
		for(x=1; x<=n; x++)
			if(G.A[x][u] > 0)
				deg_neg++;
		if(deg_neg == 0)
			add_edge(&G, n+1, u);
	}
	
	for(u=1; u<= n; u++){
		int deg_pos = 0;
		for(v =1; v<= n; v++)
			if(G.A[u][v] > 0)
				deg_pos++;
		if(deg_pos == 0)
			add_edge(&G, u, n+2);
	}
	int z, y;
	scanf("%d%d", &z, &y);
	List L;
	topo_sort(&G, &L);
	
	int t[MAX_Vertices];
	t[n+1] =0;
	for(j=2; j<=L.size; j++){
		int u = element_at(&L, j);
		t[u] = -1;
		for(x =1; x<=G.n; x++)	
			if(G.A[x][u] > 0)
				t[u] = max(t[u], t[x] + d[x]);
	}
	
	int T[MAX_Vertices];
	T[n+2] = t[n+2];
	for(j = L.size-1; j>= 1; j--){
		int u = element_at(&L, j);
		T[u] = infinity;
		for(v = 1; v<=G.n; v++)
			if(G.A[u][v] > 0)
				T[u] = min(T[u], T[v] - d[u]);
	}
//	printf("%d\n", t[n+2]);
//	for(j =1; j<=G.n; j++)
//		printf("%d-%d\n", t[j], T[j]);
	if(t[z] <= y && T[z] >=y) printf("YES");
	else printf("NO");
	
	return 0;
}


Editor is loading...