首页 > 代码库 > 洛谷 P1343 地震逃生
洛谷 P1343 地震逃生
题目描述
汶川地震发生时，四川**中学正在上课，一看地震发生，老师们立刻带领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 71 2 11 4 22 3 14 5 14 3 13 6 25 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;}
洛谷 P1343 地震逃生
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。