Untitled
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...