# Untitled

unknown
plain_text
3 years ago
3.5 kB
2
Indexable
Never
```#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++){
}
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++)
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);
}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)
}

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)
}
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;
}

```