LUỒNG CỰC ĐẠI

 LUỒNG CỰC ĐẠI

#include<stdio.h>

#define MAXN 100
#define NO_EDGE 0
#define INF 99999

//Queue

#define MAX_ELEMENTS 100 

typedef struct { 
	int data[MAX_ELEMENTS]; 
	int front, rear; 
} Queue;
 
void make_null_queue(Queue* Q) { 
	Q->front = 0; 
	Q->rear = -1; 
} 

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

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

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

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

// cau truc do thi
typedef struct{
	int C[MAXN][MAXN];	// kha nang thong qua cung 
	int F[MAXN][MAXN];	// luong tren cung
	int n;
}Graph;

// cau truc nhan label
typedef struct{
	int dir; // =0 chua co nhan ; =1 cung thuan ; =-1 cung nghich
	int pre; // dinh truoc cua dinh dang xet
	int sigma; // luong tang cua luong
}Label;

// BIEN HO TRO 
Label labels[MAXN]; // luu nhan cac dinh

//khoi tao cac luong =0
void init_flow(Graph *G){
	int u,v;
	for(u=1;u<=G->n;u++)
		for(v=1;v<=G->n;v++)
			G->F[u][v]=0;
}

void init_graph(Graph*G,int n)
{
	G->n=n;
	int i,j;
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			G->C[i][j]=NO_EDGE;	
}

// lay gia tri nho nhat trong 2 so x,y
int min(int x,int y){
	return (x<y) ? x:y;
}

int FordFullkerson(Graph *G,int s,int t){
	int u,v;
	// khoi tao luong =0 voi moi cung tren do thi
	init_flow(G);
	int sum_flow=0;
	// khoi tao hang doi Q luu tru cac dinh de duyet
	Queue Q;
	// lap 
	do{
		// buoc 1 - xoa tat ca cac nhan =0
		for(u=1;u<=G->n;u++)
			labels[u].dir=0;
		
		// gan nhan cho S
		labels[s].dir=1; // gan nhan cho s =1 
		labels[s].pre=s; // default dinh truoc s la s
		labels[s].sigma = INF; // luong dua vao la vo cung INF
		// khoi tao Q rong
		make_null_queue(&Q);
		//dua s vao Q
		enqueue(&Q,s);
		int found=0;
		// lap gan nhan cho cac dinh
		//int k=1;
		while(!empty(&Q))
		{
		//	printf("lan lap thu %d\n",k++);
			// lay 1 dinh trong Q ra la u
			int u=top(&Q); 
		//	printf("u=%d\nxoa u ra khoi Q\n",u);
			//xoa no ra khoi Q
			dequeue(&Q);
			for(v=1;v<=G->n;v++)
			{
				// xet gan nhan cho cung thuan hay cac dinh ke cua u
				if(labels[v].dir==0 && G->C[u][v]!=NO_EDGE && G->C[u][v]>G->F[u][v])
				{
		//			printf("cung thuan\n");
					labels[v].dir=1; // cung thuan
					labels[v].pre=u; // dinh ke truoc cua v la u
					labels[v].sigma=min(labels[u].sigma,G->C[u][v]-G->F[u][v]);
		//			printf("labels[%d].dir= %d\nlabel[%d].sigma=%d\n",v,labels[v].dir,v,labels[v].sigma);
					// dua v vao trong Q
		//			printf("dua %d vao Q\n",v);
					enqueue(&Q,v);
				}
				// xet gan nhan cho cung nghich hay cac dinh den u
				if(labels[v].dir==0 && G->C[v][u]!=NO_EDGE && G->F[v][u]>0)
				{
		//			printf("cung nghich\n");
					labels[v].dir = -1; // cung nghich
					labels[v].pre = u; // dinh di den v la u
					labels[v].sigma=min(labels[u].sigma,G->F[u][v]);
		//			printf("labels[%d].dir= %d\nlabel[%d].sigma=%d\n",v,labels[v].dir,v,labels[v].sigma);
					// dua v vao Q
		//			printf("dua %d vao Q\n",v);
					enqueue(&Q,v); 
				}
				
			}
			// neu t duoc gan nhan =>
				// tim duoc duong tang luong, thoat vong lap
			if(labels[t].dir!=0)
			{
		//		printf("tim duoc dir t !=0\n");
				found=1;
				break;
			}
		}
		if(found==1)
		{
			// tang luong
			int x=t;
			int sigma= labels[t].sigma;
			sum_flow+=sigma; // tang them luong
			// kiem tra xem dinh do co phai la s khong
			while(x!=s)
			{
				int u=labels[x].pre; // lay dinh truoc cua x
		//		printf("Dinh truoc la: %d\n",u);
				if(labels[x].dir>0)
				{
					
					G->F[u][x] +=sigma; // tang luong
		//			printf("tang luong F[%d][%d] = %d\n",u,x,G->F[u][x]);
				}
				else
				{
					G->F[x][u] -=sigma;
		//			printf("Giam luong F[%d][%d] = %d\n",x,u,G->F[x][u]);
				}
				x=u; 
			}
		}
		else break; // thoat vong lap
		
			
	} while(1);
	return sum_flow;
}

int main(){
	Graph G;
	//freopen("dt.txt", "r", stdin);
	int n, m, u, v, e, c;
	scanf("%d%d",&n,&m);
	init_graph(&G,n);
	
	for(e=0;e<m;e++)
	{
		scanf("%d%d%d",&u,&v,&c);
		G.C[u][v]=c;
	}
	
	int max_flow = FordFullkerson(&G,1,n);
	
	printf("Max flow: %d\n",max_flow);
		// in lat cat (X0,Y0)
	printf("X0: ");
	for(u=1;u<=n;u++)
		if(labels[u].dir!=0)
			printf("%d ",u);
	printf("\nY0: ");
	for(u=1;u<=n;u++)
		if(labels[u].dir==0)
			printf("%d ",u);
		
	return 0;
}