2268606_wa.c

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MaxV 201
#define INIT (EdgeNode *)malloc(sizeof(EdgeNode))
#define INF 21000000000000

int n, m;
__int64 MaxF;
__int64 map[MaxV][MaxV];
typedef struct node
{
	__int64 w;
	int adjvex;
	struct node *next;
}EdgeNode;
typedef struct vnode
{
	EdgeNode *firstedge;
}VertexNode;
typedef VertexNode AdjList[MaxV];
typedef struct ALGraph
{
	AdjList adjlist;
}Graphic;
void Init(Graphic *G)
{
	int i;
	int st, ed;
	__int64 w;
	EdgeNode *s;

	MaxF = 0;
	memset(map,0,sizeof(map));
	for(i = 0; i < m; i++)
		G->adjlist[i].firstedge = NULL;
	for(i = 0; i < n; i++)
	{
		scanf("%d%d%I64d",&st,&ed,&w);
		if(map[st-1][ed-1]==0)
			map[st-1][ed-1] = w;
		else
		{
			s = G->adjlist[st-1].firstedge;
			while(s)
			{
				if(s->adjvex==ed-1)
				{
					s->w += w;
					break;
				}
				s = s->next;
			}
		}
		if(w)
		{
			s = INIT;
			s->adjvex = ed-1;s->w = w;
			s->next = G->adjlist[st-1].firstedge;
			G->adjlist[st-1].firstedge = s;
		}
	}
}

int bfs(Graphic *G)
{
	int mark = 0;
	int f, r, q, p;
	int pre[MaxV], visited[MaxV];
	int queue[MaxV];
	__int64 F[MaxV];
	__int64 C;
	EdgeNode *s;

	f = r = -1;
	memset(visited,0,sizeof(visited));
	memset(pre,0,sizeof(pre));
	memset(F,0,sizeof(F));
	visited[0] = 1;queue[++f] = 0;pre[0] = -1;
	while(f!=r)
	{
		++r;
		q = queue[r];
		if(q==m-1)
		{
			mark = 1;
			break;
		}
		s = G->adjlist[q].firstedge;
		while(s)
		{
			p = s->adjvex;
			if(visited[p]==0)
			{
				visited[p] = 1;
				queue[++f] = p;
				pre[p] = q;
				F[p] = s->w;
			}
			s = s->next;
		}
	}
	if(mark)
	{
		C = INF;
		while(pre[q]!=-1)
		{
			if(F[q]<C)
				C = F[q];
			q = pre[q];
		}
		q = m-1;
		while(pre[q]!=-1)
		{
			s = G->adjlist[pre[q]].firstedge;
			if(F[q]>C)
			{
				if(s->adjvex==q)
					s->w -= C;
				else
				{
					while(s->next)
					{
						if(s->next->adjvex==q)
						{
							s->next->w -= C;
							break;
						}
						s = s->next;
					}
				}
				s = G->adjlist[q].firstedge;
				while(s)
				{
					if(s->adjvex==pre[q])
					{
						s->w += C;
						goto M1;
					}
					s = s->next;
				}
				s = INIT;
				s->adjvex = pre[q];
				s->w = C;
				s->next = G->adjlist[q].firstedge;
				G->adjlist[q].firstedge = s;
				M1:;
			}
			else
			{
				if(s->adjvex==q)
					G->adjlist[pre[q]].firstedge = s->next;
				else
				{
					while(s->next)
					{
						if(s->next->adjvex==q)
						{
							s->next = s->next->next;
							break;
						}
						s = s->next;
					}
				}
			}
			q = pre[q];
		}
		MaxF += C;
	}
	return mark;
}

void Maxflow(Graphic *G)
{
	while(bfs(G));
	printf("%I64d\n",MaxF);
}

int main()
{
	Graphic G;

	while(scanf("%d%d",&n,&m)==2)
		Init(&G),Maxflow(&G);
	return 1;
}