这应该是个有向图吧?用最大流做.用dijkstra搜索路径,结果加最小的边权,然后该边的边权取无穷大,其他减去这个边权,再搜索,直到prev[n]为0.有错吗?~~~

#include<stdio.h>
#include<string.h>
#define MAX 2000000000
int n,m,c[201][201],dist[201],s,e,cost,prev[201],maxf;

void dijkstra()
{
	int i1,j1,tmp,u,tmp1;
	bool s[201];
	int v = 1;
	for (i1 = 1;i1 <= n;i1++)
	{
		dist[i1] = c[v][i1];
		s[i1] = false;
		if (dist[i1] == MAX)
			prev[i1] = 0;
		else
			prev[i1] = v;
	}
	dist[v] = 0;
	s[v] = true;
	for (i1 = 1;i1 < n;i1++)
	{
		tmp = MAX;
		u = v;
		for (j1 = 1;j1 <= n;j1++)
		{
			if ((!s[j1]) && (dist[j1] < tmp))
			{
				u = j1;
				tmp = dist[j1];
			}
		}
		s[u] = true;
		for (j1 = 1;j1 <= n;j1++)
		{
			if ((!s[j1]) && (c[u][j1] < MAX))
			{
				tmp1 = dist[u] + c[u][j1];
				if (tmp1 < dist[j1])
				{
					dist[j1] = tmp1;
					prev[j1] = u;
				}
			}
		}
	}
}

int main()
{
	int i,j;
	while (scanf( "%d %d", &m, &n ) != EOF) //m是边,n是点
	{
		maxf = 0;
		for (i = 1;i <= n;i++)
		{
			for (j = 1;j <= n;j++)
			{
				if (i == j)
					c[i][j] = 0;
				else
					c[i][j] = MAX;
			}
		}
		for (i = 0;i < m;i++)
		{
			scanf("%d%d%d",&s,&e,&cost);
			if (c[s][e] == MAX)
				c[s][e] = cost;
			else
				c[s][e] += cost;
		}
		while (1)
		{
			dijkstra();
			if (prev[n] == 0)
				break;
			else
			{
				i = n;
				j = MAX;
				while (i != 1)
				{
					if (j > c[prev[i]][i])
						j = c[prev[i]][i];	
					i = prev[i];
				}
				i = n;
				while (i != 1)
				{
					if (c[prev[i]][i] == j)
						c[prev[i]][i] = MAX;
					else
						c[prev[i]][i] = c[prev[i]][i] - j;
					i = prev[i];
				}
				maxf += j;
			}
		}
		printf("%d\n",maxf);
	}
	return 0;
}