沉重的貨物

? ? ? ? ? ? ? Time Limit:?1000ms ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??Memory Limit:?65536KB 64-bit integer IO format:?%lld????? Java class name:?Main

?

CUITCPC是一個(gè)專(zhuān)門(mén)生產(chǎn)大型貨運(yùn)火車(chē)的工廠(chǎng)。他們的新型貨運(yùn)火車(chē)XX V1.0，是如此之大，以至于可以運(yùn)輸?shù)呢浳锏闹亓坎⒉蝗Q于那個(gè)火車(chē)本身，而只是受限于你所通過(guò)的鐵路的承重。

給你出發(fā)和目標(biāo)城市，你的任務(wù)就是求出火車(chē)從初始城市到目標(biāo)城市的最大載重。

Input

?

輸入可能包括一組或者多組測(cè)試數(shù)據(jù)。每一個(gè)測(cè)試數(shù)據(jù)的前兩行是兩個(gè)整數(shù):城市的數(shù)量n(2<=n<=1000)和鐵路的條數(shù)r(1<=r<= 19900)。

緊接著是r行，每一行描述一條連接兩個(gè)城市的鐵路以及這段鐵路所能承受的最大重量。城市名不會(huì)超過(guò)30個(gè)字符，也不會(huì)有空白字符出現(xiàn)在城市名中。承重是一個(gè)0-10000的整數(shù)。鐵路都是雙向的。

最后一行是兩個(gè)城市的名字：初始城市和目標(biāo)城市。

輸入的結(jié)束條件是n和r都為0

Output

?

對(duì)于每一組測(cè)試數(shù)據(jù)

輸出包括3行：

l? 一行輸出"Scenario #x"，其中x是測(cè)試數(shù)據(jù)的組數(shù)

l? 一行輸出"y tons"，其中y表示最大載重量

l? 一個(gè)空行

Sample Input

4 3 ACM ICPC 100 ICPC World 80 World CPC 120 ACM CPC 5 5 ACM ICPC 100 ICPC World 80 World CPC 120 ACM Chengdu 220 Chengdu CPC 170 CPC ACM 0 0

Sample Output

Scenario #1 80 tonsScenario #2 170 tons

這是昨天晚上比賽的一道題，個(gè)人感覺(jué)這題還不錯(cuò)，只可惜當(dāng)時(shí)沒(méi)有做出來(lái)。讀完題看出來(lái)了是一道最大流的題目，但我沒(méi)有仔細(xì)的學(xué)過(guò)網(wǎng)絡(luò)流，我按照書(shū)上的模板打完之后又發(fā)現(xiàn)不能直接套模板。比賽完聽(tīng)隊(duì)友說(shuō)也可以用最小生成樹(shù)或者搜索來(lái)做，看來(lái)我想的太少了。

今天用最小生成樹(shù)的思想寫(xiě)了一下這個(gè)題，每次往集合中添加一個(gè)距離起點(diǎn)最遠(yuǎn)的點(diǎn)，直到把終點(diǎn)添加進(jìn)去，然后從這些邊中選擇一個(gè)最小值就是所求的答案。也許你會(huì)問(wèn)：把終點(diǎn)添加進(jìn)去就結(jié)束，那其他沒(méi)有添加的點(diǎn)怎么辦？會(huì)不會(huì)影響最終結(jié)果？ ?答案是不會(huì)。因?yàn)槲覀円蟮氖亲畲笾?#xff0c;每次添加的都是較長(zhǎng)的邊，即使通過(guò)其他路徑可以到達(dá)終點(diǎn)，但是通過(guò)其他路徑得到的最大值肯定不會(huì)超過(guò)我們求出的結(jié)果。 #include<iostream> #include<cstring> #include<string> #include<map> using namespace std; const int INF = 0x3fffffff; const int N = 1e4; int n, m, Min; int cap[N][N], low[N], vis[N]; void Init(int n) {for(int i = 0; i <= n; i++)for(int j = 0; j <= n; j++)cap[i][j] = -INF; } void Prim(int s, int e) {int i, j;memset(vis, 0, sizeof(vis));memset(low, -1, sizeof(low));for(i = 1; i <= n; i++)if(cap[s][i] != -INF)low[i] = cap[s][i];vis[s] = 1;for(i = 1; i < n; i++){int mmax = -1, pos;for(j = 1; j <= n; j++)if(!vis[j] && low[j] > mmax)mmax = low[pos = j];if(mmax == -1) break; //此句可加可不加，執(zhí)行此句時(shí)肯定加入了已經(jīng)n-1條邊Min = Min < mmax ? Min : mmax;if(pos == e) break;vis[pos] = 1;for(j = 1; j <= n; j++)if(!vis[j] && cap[pos][j] > low[j])low[j] = cap[pos][j];} } int main() {int i, j, t, w, cas = 1;map<string, int> mp;string str1, str2;while(cin >> n >> m){if(!n && !m) break;Min = INF;mp.clear();Init(n);t = 1;for(i = 0;i < m; i++){cin >> str1 >> str2 >> w;if(mp.find(str1) == mp.end())mp[str1] = t++;if(mp.find(str2) == mp.end())mp[str2] = t++;int x = mp[str1], y = mp[str2];cap[x][y] = cap[y][x] = w;}cin >> str1 >> str2;Prim(mp[str1], mp[str2]);cout << "Scenario #" << cas++ << endl;cout << Min << " tons" << endl;cout << endl;}return 0; }

總結(jié)

以上是生活随笔為你收集整理的bnuoj 20950 沉重的货物 (最小生成树）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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