SSL-ZYC 1616 1762 工厂的烦恼

本文主要是介绍SSL-ZYC 1616 1762 工厂的烦恼，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目大意：
　某工厂发现厂里的机器在生产产品时要消耗大量的原材料，也就是说，有大量的原材料变成了废物。因此厂里想找出消耗原材料最大的一条生产线路进行改造，以降低成本。厂里的生产线路是一个有向无环网络，有N台机器分别代表网络中的N个结点。弧< I,j >(i < j)表示原材料从机器i传输到机器j的损耗数量。
比如：
这里写图片描述
这个流水线中，耗材最大的是6->3->4->5，一共耗材4+1+6=11

思路：
这道题是一个最短路径问题，值得注意的是，它是一个有向图，也就是说，上图点1可以到点2，但是点2不能到点1！
然后，由于这道题需要求出每一个点到另外一个点的耗材，所以要用Floyed算法。

然后，这虽然是一道最短路径问题，但是我们要求的是耗材最大的流水线，而不是最少的一条！所以所谓的“最短路径问题”就变成了“最长路径问题”！

代码：

#include <iostream>
#include <cstdio>
using namespace std;
int f[101][101],n,m,maxn;int main()
{int x,y,q;scanf("%d%d",&n,&m);for (int i=1;i<=m;i++){scanf("%d%d%d",&x,&y,&q);f[x][y]=q;  //记录流水线以及耗材 }for (int k=1;k<=n;k++)for (int i=1;i<=n;i++)for (int j=1;j<=n;j++)  //Floyed算法if (f[i][j]<f[i][k]+f[k][j]&&i!=j&&j!=k&&k!=i&&f[i][k]!=0&&f[k][j]!=0)  //如果有耗材更多的一条流水线而且符合要求 f[i][j]=f[i][k]+f[k][j];maxn=0;for (int i=1;i<=n;i++)for (int j=1;j<=n;j++)if (maxn<f[i][j]) maxn=f[i][j];  //寻找耗材最多的流水线 printf("%d\n",maxn);  //输出不解释 return 0;
}