BÀI TOÁN THI CÔNG

BÀI TOÁN THI CÔNG

 //Thi Cong // Adjacency Matrix (Vertices-Vertices) [Directed]

#include <stdio.h>

#define MAX_ELEMENTS 100

//List Structure
typedef int ElementType;
typedef struct {
ElementType data[MAX_ELEMENTS];
int size;
}List;

//Stack Structure
typedef struct
{
    int data[MAX_ELEMENTS];
    int size;
}Stack;

//Queue Structure
typedef struct
{
    int data[MAX_ELEMENTS];
    int front, rear;
}Queue;

/* Init List */

//Make null a list
void make_null_list(List* L) {
    L->size = 0;
}

//Pust List
void push_list(List* L, ElementType x) {
    L->data[L->size] = x;
    L->size++;
}

//Return an element at list
ElementType element_at_list(List* L, int i) {
    return L->data[i-1];
}

//Count amount element in list
int count_list(List* L) {
    return L->size;
}

//Empty a list
int empty_list(List *L)
{
    return L->size == 0;
}

//Copy list
void copy_list(List* L1, List* L2)
{
	int i;
	make_null_list(L1);
	for(i = 1; i <= L2->size; i++)
	{
		push_list(L1, element_at_list(L2, i));
	}
}

/* Init Queue */

//Make null a queue
void make_null_queue(Queue *Q)
{
    Q->front = 0;
    Q->rear = -1;
}

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

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

//Pop Queue
void pop_queue(Queue *Q)
{
    Q->front++;
}

//Empty a Queue
int empty_queue(Queue *Q)
{
    return Q->front>Q->rear;
}

/* Init Stack */

//Make null a stack
void make_null_stack(Stack *S)
{
    S->size = 0;
}

//Push Stack
void push_stack(Stack *S, int x)
{
    S->data[S->size] = x;
    S->size++;
}

//Top stack
int top_stack(Stack *S)
{
    return S->data[S->size - 1];
}

//Pop stack
int pop_stack(Stack *S)
{
    return S->size--;
}

//Empty a stack
int empty_stack(Stack *S)
{
    return S->size == 0;
}

#define MAX 200
#define INFINITY 999999

int d[MAX];
int t[MAX];
int T[MAX];

//Graph Structure
typedef struct
{
    int n;
    int A[MAX][MAX];
}Graph;


/* Init A Basic Graph */

//Init an empty graph
void init_graph(Graph* G, int n)
{
    int i, j;
    G->n = n;
    for(i = 1;  i <= n; i++)
        for(j = 1; j <= n; j++)
            G->A[i][j] = 0;
}

// Add an edge
void add_vecto(Graph *G, int x, int y)
{
    G->A[x][y] = 1;
    G->A[y][x] = -1;
}

//Scan any edge
void scan_vecto_graph(Graph *G)
{
	int n,u,v,x;
//	freopen("DuAnXayNha.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_vecto(G,x,u);
		}while(x>0);
}
	
		//them cung noi alpha 
	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_vecto(G,n+1,u);
	}
	//them cung noi beta
	for(u=1;u<=n;u++){
		int deg_pos = 0;
		for(v=1;v<=n;v++)
			if(G->A[u][v]>01)
				deg_pos++;
		if(deg_pos ==0 )
			add_vecto(G,u,n+2);
	}
}

//Scan a matrix
void scan_obo_graph(Graph *G)
{
    int n;
	scanf("%d", &n);
	init_graph(G, n);
    int i, j;
    G->n = n;
    for(i = 1; i <= n; i++)
    {
        for(j = 1; j <= n; j++)
        {
            scanf("%d", &G->A[i][j]);
        }
    }
}

//Print a matrix
void print_graph(Graph *G)
{
    int i, j;
    printf("\nMatrix %dx%d: \n", G->n, G->n);
    for(i = 1; i <= G->n; i++)
    {
        for(j = 1; j <= G->n; j++)
        {
            printf("%d  ", G->A[i][j]);
        }
        printf("\n");
    }
}


//Return IN degree of a vertice
int degree_in(Graph* G, int x)
{
    int y, deg = 0;
    for(y = 1; y <= G->n; y++)
        if(G->A[x][y] < 0)
            deg++;
    return deg;
}

//Has edge
int has_edge(Graph* G, int x, int y)
{
    return ((G->A[x][y] != 0) && (G->A[y][x] != 0)) ? 1 : 0;
}

//Check Adjacency
int check_direction(Graph* G, int x, int y)
{
    return ((G->A[x][y] == 1) && (G->A[y][x] == -1)) ? 1 : 0;
}

//Return Out Vertical Neighbor List ++
List neighbors_out(Graph *G, int x)
{
    int y;
    List list;
    make_null_list(&list);
    for(y = 1; y <= G->n; y++)
        if(check_direction(G, x, y) && has_edge(G, x, y))
        {
            push_list(&list, y);
        }
   return list;
}

void TopoSort(Graph* G, List* L)
{
	int u, d[MAX];
	Queue Q;
	make_null_queue(&Q);
	for(u = 1; u <= G->n; u++)
		d[u] = 0;
	for(u = 1; u <= G->n; u++)
		d[u] = degree_in(G, u);
	for(u = 1; u <= G->n; u++)
		if(d[u] == 0)
			push_queue(&Q, u);
	make_null_list(L);
	while(!empty_queue(&Q))
	{
		int u = top_queue(&Q);
		pop_queue(&Q);
		push_list(L, u);
		int v;
		for(v = 1; v <= G->n; v++)
		{
			if(has_edge(G, u, v))
			{
				d[v]--;
				if(d[v] == 0)
					push_queue(&Q, v);
			}
		}
	}
}

int min(int a, int b)
{
	return a < b ? a : b;
}

int max(int a, int b)
{
	return a < b ? b : a;
}

void ThiCong(Graph* G, List* L)
{
	int n = G->n-2;
	t[n+1]=0;
	int i ,v;
	for(i=2;i<=L->size;i++){
		int u=element_at_list(L,i);
		t[u]=-1;
		for (v = 1; v <= G->n; v++)
			if(check_direction(G, v, u))
				t[u]=max(t[u],t[v]+d[v]);
	}
	// tinh T[u]
	T[n+2]=t[n+2];
	for(i=L->size-1;i>=1;i--){
		int u=element_at_list(L,i);
		T[u]=INFINITY;
		for (v = 1; v <= G->n; v++)
			if(check_direction(G, u, v))
				T[u]=min(T[u],T[v]-d[u]);
	}
}

int main()
{
	Graph dothi;
//	freopen("dt.txt","r",stdin);
	scan_vecto_graph(&dothi);
	List L;
	TopoSort(&dothi, &L);
	ThiCong(&dothi, &L);
	int i;
	printf("%d\n", T[dothi.n]);
	for(i = 1; i <= dothi.n; i++)
		printf("%d-%d\n", t[i], T[i]);
	return 0;
}