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
题解：
最长路，把小于号改一改就好了。
代码：
var
f:
array[
0..
500,
0..
500]
of longint;
n,m,i,j,k,x,y:longint;
begin
readln(n,m);
for i:=
1 to n
do
for j:=
1 to n
do
f[i,j]:=-
1000000;
for i:=
1 to m
do
begin
read(x,y);
readln(f[x,y]);
end;
for k:=
1 to n
do
for i:=
1 to n
do
for j:=
1 to n
do
if (i<>j)
and(j<>k)
and(i<>k)
then
if f[i,k]+f[k,j]>f[i,j]
then
f[i,j]:=f[i,k]+f[k,j];
x:=-maxlongint;
for i:=
1 to n
do
for j:=i+
1 to n
do
if (i<>j)
and(f[i,j]>x)
then x:=f[i,j];
writeln(x);
end.
转载请注明原文地址: https://ju.6miu.com/read-968143.html
