工厂的烦恼（Floyed）

工厂的烦恼

Description
　　某工厂发现厂里的机器在生产产品时要消耗大量的原材料，也就是说，有大量的原材料变成了废物。因此厂里想找出消耗原材料最大的一条生产线路进行改造，以降低成本。厂里的生产线路是一个有向无环网络，有N台机器分别代表网络中的N个结点。弧< I,j >(i < j)表示原材料从机器i传输到机器j的损耗数量。
Input
第一行是两个整数N，M（N<=100,M<=1000），分别表示网络的结点个数和弧数。第二行至M+1行，每行三个整数A，B，C，表示弧上的损耗为C。
Output
仅一个整数，为损耗最大的线路的损耗量。
Sample Input
5 5
1 2 2
2 4 9
1 3 7
3 4 1
4 5 6
Sample Output
17
分析
这题我用的是Floyed算法
可以参考
最短路径问题（最短路径）（Floyed）（Dijkstra）
注意：
1.要求最大值
2.只要判断a[i][k]和a[k][j]是否存在就行了，不需要再判断a[i][j]是否存在，否则会错（举例：1可以到2，2可以到3，那么1也可以到3,如图：）

AC代码

#include<iostream>
using namespace std;
int n,m,A,B,C,a[105][105];
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		cin>>A>>B>>C;
		a[A][B]=C;//有向图
	}
	for(int k=1;k<=n;k++)//标准五行代码
	 for(int i=1;i<=n;i++)
	  for(int j=1;j<=n;j++)
	   if(i!=j&&i!=k&&j!=k&&a[i][k]!=0&&a[k][j]!=0)//判断是否存在
	    a[i][j]=max(a[i][j],a[i][k]+a[k][j]);//找权值大的
	m=0;
	for(int i=1;i<=n;i++)//找最大
	 for(int j=1;j<=n;j++)
	  m=max(m,a[i][j]);
	cout<<m;      
}

谢谢