题意和解决回路匹配的思路如同hdu3488

(这里我第一次想到最短路，但是对于有回路这个不知道怎么处理，后来看了别人的解题报告才知道KM匹配，但是看到KM之后就自己想...想了很久....还是不知道回路这个地方怎么匹配......其实应该这样来想....总共有N个城市....如果是要形成回路..那么就是环，那么每一个城市都要和指向的城市匹配一次，也要被一个城市指向自己匹配一次...那么匹配的时候我们把所有的N个城市分成两拨，对于每一个城市都匹配一次就得到了一个完全匹配(既每个点都匹配一次，也就是每一个城市匹配一次、被匹配一次).....那么还有一个地方要注意的是：这里有重边...我们应该选择小的边更新)

这里唯一有一点点不同的就是可以存在无回路的情况，那就是有一个点或者多个点没有匹配到.....

那么在代码中体现出来：

// 31MS 272K

#include<stdio.h>

#include<string.h>

#define MAX 101

#define INF 1<<30-1

int N,M;

int map[MAX][MAX];

int lx[MAX],ly[MAX],link[MAX],slar[MAX];

bool visx[MAX],visy[MAX];

bool dfs(int x)

{

	visx[x] = true;

	for(int y = 1; y <= N; y ++)

	{

		if(visy[y]) continue;// || x == y

		int t = lx[x] + ly[y] - map[x][y];

		if(t == 0)

		{

			visy[y] = true;

			if(link[y] == -1 || dfs(link[y]))

			{

				link[y] = x;return true;

			}

		}

		else if(slar[y] > t) slar[y] = t;

	}

	return false;

}

int KM()

{

	int i,j;

	memset(ly,0,sizeof(ly));

	memset(link,-1,sizeof(link));

	for(i = 1 ;i <= N;i ++)

	{

		lx[i] = -INF;

		for(j = 1; j <= N; j ++)

			if(lx[i] < map[i][j])	lx[i] = map[i][j];

	}

	for(int x = 1; x <=N; x ++)

	{

		for(i = 1; i <= N ; i ++) slar[i] = INF;

		while(1)

		{

			memset(visx,false,sizeof(visx));

			memset(visy,false,sizeof(visy));

			if(dfs(x)) break;

			int d = INF;

			for(i = 1; i <= N;i ++)

				if(!visy[i] && d > slar[i]) d = slar[i];

			for(i = 1; i <= N; i ++)

				if(visx[i]) lx[i] -= d;

			for(i = 1; i <= N; i ++)

				if(visy[i]) ly[i] += d;

				else  slar[i] -= d;

		}

	}

	int ans = 0;bool flag = false;

	for(i = 1; i <= N; i ++)

		if(link[i] == -1 || map[link[i]][i] == -INF)//这里判断匹配不到的情况

		{

			flag=true;break;

		}

	if(flag) ans = 1;

	return -ans;

}

int main()

{

	int i,j;

	int a,b,c;

	while(~scanf("%d%d",&N,&M))

	{

		for(i = 1; i <= N; i ++)

			for(j = 1; j <= N; j ++)

				map[i][j]=-INF;

		while(M -- )

		{

			scanf("%d%d%d",&a,&b,&c);

			map[a][b] = map[a][b] > -c ? map[a][b] : -c;//重边选择

		}

		printf("%d\n",KM());

	}

	return 0;

}

个人愚昧观点..欢迎指正与讨论