工廠的煩惱

ssl 1762

題目大意：

求一個圖中最長的路線的長度

原題：

Description

某工廠發(fā)現(xiàn)廠里的機(jī)器在生產(chǎn)產(chǎn)品時(shí)要消耗大量的原材料，也就是說，有大量的原材料變成了廢物。因此廠里想找出消耗原材料最大的一條生產(chǎn)線路進(jìn)行改造，以降低成本。廠里的生產(chǎn)線路是一個有向無環(huán)網(wǎng)絡(luò)，有N臺機(jī)器分別代表網(wǎng)絡(luò)中的N個結(jié)點(diǎn)。弧< I,j >(i < j)表示原材料從機(jī)器i傳輸?shù)綑C(jī)器j的損耗數(shù)量。

Input

第一行是兩個整數(shù)N，M（N<=100,M<=1000），分別表示網(wǎng)絡(luò)的結(jié)點(diǎn)個數(shù)和弧數(shù)。第二行至M+1行，每行三個整數(shù)A，B，C，表示弧上的損耗為C。

Output

僅一個整數(shù)，為損耗最大的線路的損耗量。

Sample Input

5 5 1 2 2 2 4 9 1 3 7 3 4 1 4 5 6

Sample Output

17

解題思路：

直接用Floyed求出最長路即可

代碼：

#include<cstdio> #include<cstring> #include<iostream> using namespace std; int n,m,x,y,c,ans,a[105][105]; int main() {scanf("%d %d",&n,&m);for (int i=1;i<=m;++i){scanf("%d %d %d",&x,&y,&c);a[x][y]=c;//記錄ans=max(c,ans);//求最大}for (int k=1;k<=n;++k)for (int i=1;i<=n;++i)for (int j=1;j<=n;++j)if (a[i][k]&&a[k][j])//沒有連接的就不連a[i][j]=max(a[i][j],a[i][k]+a[k][j]),ans=max(a[i][j],ans);//求最長路和求最大printf("%d",ans);//輸出 }

總結(jié)

以上是生活随笔為你收集整理的【Floyed】工厂的烦恼（ssl 1762）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。