题目链接: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 ;
}

最新文章

  1. xib和storyBoard哪些事之UIimage和按钮注意事项
  2. 使用wex5得到的一些教训
  3. CSS权威指南 - 基础视觉格式化 3
  4. iOS数据本地持久化
  5. tomcat http 文件下载
  6. eclipse打jar包步骤
  7. kettle
  8. 反射+javacsv+scv文件构建资源获取
  9. iOS调节系统音量
  10. Android基础之CountDownTimer 倒计时类
  11. Linux网络管理——ISO/OSI七层模型
  12. i++和++i以及左值,右值
  13. 2017-02-19C#基础 - 数据类型与类型转换
  14. 用javascript动态改变网页文字大小
  15. Spring中@Value标签的使用详解
  16. 【Node100In1】01.去异步,解决掉Node.js万恶的回调陷阱
  17. [development][libhtp] libhtp 启用debug模式
  18. @Resource无法import相关
  19. excel 错误提示以及其他基础知识
  20. Redis踩过的坑

热门文章

  1. 疯狂LCM
  2. bzoj2957楼房重建——线段树
  3. PYTHON 异常处理 二 TRY 模块
  4. io_service work 的作用
  5. Android开发相关工具(eclipse篇)
  6. TypeScript完全解读(26课时)_14.ES6和Nodejs中的模块
  7. 18.Consent 实现思路介绍
  8. Lombok减少代码冗余量
  9. Qt-MVC图形视图框架初识
  10. 洛谷 - P1552 - 派遣 - 左偏树 - 并查集