題目描述

汶川地震發生時，四川**中學正在上課，一看地震發生，老師們立刻帶領x名學生逃跑，整個學校可以抽象地看成一個有向圖，圖中有n個點，m條邊。1號點為教室，n號點為安全地帶，每條邊都只能容納一定量的學生，超過樓就要倒塌，由于人數太多，校長決定讓同學們分成幾批逃生，只有第一批學生全部逃生完畢后，第二批學生才能從1號點出發逃生，現在請你幫校長算算，每批最多能運出多少個學生，x名學生分幾批才能運完。

輸入輸出格式

輸入格式：

?

第一行3個整數n,m,x(x<2^31,n<=200,m<=2000)；以下m行，每行三個整數a,b,c（a1,a<>b,0描述一條邊，分別代表從a點到b點有一條邊，且可容納c名學生。

?

輸出格式：

?

兩個整數，分別表示每批最多能運出多少個學生，x名學生分幾批才能運完。如果無法到達目的地（n號點）則輸出“Orz Ni Jinan Saint Cow!”

?

輸入輸出樣例

輸入樣例#1：
6 7 7 1 2 1 1 4 2 2 3 1 4 5 1 4 3 1 3 6 2 5 6 1 輸出樣例#1：
3 3

說明

【注釋】

比如有圖

1 2 100

2 3 1

100個學生先沖到2號點，然后1個1個慢慢沿2-3邊走過去

18神牛規定這樣是不可以的……

也就是說，每批學生必須同時從起點出發，并且同時到達終點

?

最大流 裸題

屠龍寶刀點擊就送

#include <cstring> #include <cstdio> #include <vector> #include <queue> #define inf 0x7fffffusing namespace std;bool vis[301]; int maxn,cs,deep[301],Answer,x,m,n,mp[301][301],i,j; bool bfs(int s,int t) {queue<int>q;memset(deep,-1,sizeof(deep));q.push(s);deep[s]=0;while(!q.empty() ){int Tp=q.front() ;q.pop();for(i=1;i<=n;++i){if(mp[Tp][i]&&deep[i]==-1){deep[i]=deep[Tp]+1;if(i==n) return 1;else q.push(i); }}}return 0; } void dfs(int s,int t) {memset(vis,0,sizeof(vis));vis[s]=1;vector<int>vec;vec.push_back(s);while(!vec.empty() ){int p=vec.back() ;if(p==n){int k,minx=inf;for(i=1;i<vec.size() ;++i){int u=vec[i-1],v=vec[i];if(mp[u][v]>0&&mp[u][v]<minx){k=u;minx=mp[u][v];}}Answer+=minx;cs++;maxn=max(maxn,minx);for(i=1;i<vec.size() ;++i){int u=vec[i-1],v=vec[i];mp[u][v]-=minx;mp[v][u]+=minx;}while(!vec.empty() &&vec.back() !=k){vis[vec.back() ]=0;vec.pop_back();}}else{int l;for(l=1;l<=n;++l){if(mp[p][l]>0&&!vis[l]){vec.push_back(l);vis[l]=1; break;}}if(l>n) vec.pop_back();}} } void Dinic(int s,int t) {while(bfs(s,t))dfs(s,t); } int main() {scanf("%d%d%d",&n,&m,&x);int u,v,l;for(i=0;i<m;++i){scanf("%d%d%d",&u,&v,&l);mp[u][v]+=l;}Dinic(1,n);if(Answer==0)printf("Orz Ni Jinan Saint Cow!");else printf("%d %d\n",Answer,(x%Answer==0)?x/Answer:x/Answer+1);return 0; }

?

轉載于:https://www.cnblogs.com/ruojisun/p/6506912.html

總結

以上是生活随笔為你收集整理的洛谷 P1343 地震逃生的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。