[Luogu1343]地震逃生 最大流
2024-08-28 22:26:00
题目链接:https://www.luogu.org/problem/show?pid=1343
dinic跑最大流。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int INF=<<;
int inline readint(){
// int Num;char ch;
// while((ch=getchar())<'0'||ch>'9');Num=ch-'0';
// while((ch=getchar())>='0'&&ch<='9') Num=Num*10+ch-'0';
// return Num;
int Num;
scanf("%d",&Num);
return Num;
}
int N,M,X;
int to[],ne[],c[],fir[],cnt=;
void Add(int x,int y,int z){
to[cnt]=y,ne[cnt]=fir[x],c[cnt]=z,fir[x]=cnt++;
to[cnt]=x,ne[cnt]=fir[y],c[cnt]=,fir[y]=cnt++;
}
int S,T;
int bfn[],ti=;
int cur[],q[],dep[];
bool Bfs(){
int head=,tail=;
q[]=S;
bfn[S]=++ti;
dep[S]=;
int u;
while(head<=tail){
u=q[head++];
for(int i=fir[u];i!=-;i=ne[i]){
int v=to[i];
if(bfn[v]!=bfn[u]&&c[i]){
bfn[v]=bfn[u];
dep[v]=dep[u]+;
q[++tail]=v;
}
}
}
return bfn[T]==bfn[S];
}
int Dfs(int u,int mxf){
if(!mxf||u==T) return mxf;
int flow=,f;
for(int &i=cur[u];i!=-;i=ne[i]){
int v=to[i];
if(dep[v]==dep[u]+&&(f=Dfs(v,min(mxf,c[i])))>){
c[i]-=f;
c[i^]+=f;
flow+=f;
mxf-=f;
if(!mxf) break;
}
}
return flow;
}
int Dinic(){
int ret=;
while(Bfs()){
memcpy(cur,fir,sizeof(fir));
ret+=Dfs(S,INF);
}
return ret;
}
int main(){
N=readint();
M=readint();
X=readint();
S=;
T=N;
memset(fir,-,sizeof(fir));
for(int i=;i<=M;i++){
int a=readint(),
b=readint(),
c=readint();
Add(a,b,c);
}
int mx=Dinic();
if(!mx){
puts("Orz Ni Jinan Saint Cow!");
return ;
}
printf("%d %d\n",mx,X/mx+(X%mx?:));
return ;
}
最新文章
- xib和storyBoard哪些事之UIimage和按钮注意事项
- 使用wex5得到的一些教训
- CSS权威指南 - 基础视觉格式化 3
- iOS数据本地持久化
- tomcat http 文件下载
- eclipse打jar包步骤
- kettle
- 反射+javacsv+scv文件构建资源获取
- iOS调节系统音量
- Android基础之CountDownTimer 倒计时类
- Linux网络管理——ISO/OSI七层模型
- i++和++i以及左值,右值
- 2017-02-19C#基础 - 数据类型与类型转换
- 用javascript动态改变网页文字大小
- Spring中@Value标签的使用详解
- 【Node100In1】01.去异步,解决掉Node.js万恶的回调陷阱
- [development][libhtp] libhtp 启用debug模式
- @Resource无法import相关
- excel 错误提示以及其他基础知识
- Redis踩过的坑