最大流加强 dinic+当前弧优化

时间:2021-01-23 10:36:45

qyy开始练习网络流啦 , 啊 ,蒟蒻只会套版 ,很裸的题 , 我连题都不想发了 ,可以参考我的代码(虽然我也是看的别人的

 #include <iostream>
#include <cstring>
#include <vector>
#include <cstdio>
#include <queue>
const int N = + , M = + ;
using namespace std ;
int n , m ;
int tot , head[N] ;
long long ans;
struct id
{
int to , nxt ;
long long val ;
} edge[M<<] ;
queue< int > Q;
int dis[N] ,cur[N]; inline void Init( )
{
freopen( "NSOOJ10477.in" , "r" , stdin ) ;
freopen( "NSOOJ10477.out" , "w" , stdout ) ;
} int read( )
{
char ch = getchar( ) ; int k = , ret = ;
while( ch > '' || ch < '' ) { if( ch == '-' ) k = - ; ch = getchar( ) ; }
while( ch <= '' && ch >= '' ) ret = ret * + ch - '' , ch = getchar( ) ;
return ret * k ;
} void add( int u , int v , int c )
{
edge[++tot].to = v , edge[tot].nxt = head[u] ;
edge[tot].val = c , head[u] = tot ;
} void input( )
{
n = read( ) , m = read( ) ;
memset( head , - , sizeof( head ) ) ;
tot = ;
for( int x = ; x <= m ; ++x )
{
int a, b , c ;
a = read( ) , b = read( ) , c = read( ) ;
add( a, b , c ) ;
add( b , a , ) ;
}
} bool bfs( )
{
memset( dis , - , sizeof(dis) ) ;
Q.push( ) ; dis[] = ;
while( !Q.empty( ) )
{
int u = Q.front( ) ; Q.pop( ) ;
for( int i = head[u] ; ~i ; i = edge[i].nxt )
{ int v = edge[i].to ;
if( dis[v] < && edge[i].val > )
{
dis[v] = dis[u] + ; Q.push( v ) ;
} }
}
// cout<<endl;
if( dis[n] > ) return true ;
return false ;
} long long int dfs( int u , int inf )
{
long long int ans = 0ll , cost = 0ll;
if( u == n ) return inf ;
for( int i = cur[u] ; ~i ; i = edge[i].nxt )
{
int v = edge[i].to ;
if( dis[v] != dis[u] + ) continue ;
ans = dfs( v , min( inf - cost , edge[i].val ) ) ;
edge[i].val -= ans ;
edge[i^].val += ans ;
if( edge[i].val ) cur[u] = i ;
cost += ans ;
if( cost == inf ) return inf ;
}
if( !cost ) dis[u] = - ;
return cost ;
} void sov( )
{
ans = ;
while( bfs( ) )
{
int now ;
for( int i = ; i <= n ; ++i ) cur[i] = head[i] ;
ans += dfs( , << ) ;
}
printf( "%lld" , ans ) ;
} int main( )
{
// Init( ) ;
input( ) ;
sov( ) ;
// fclose( stdin ) ;
// fclose( stdout ) ;
return ;
}

重新贴板,和上面的程序几乎没什么区别,码风固定了,值得开心。

 #include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
const int N = , M = 3e5 + , inf = << ;
using namespace std;
int n, m, head[N], cnt, dis[N],cur[N];
queue<int>Q;
struct edge
{
int nxt,to,vi;
} E[M<<]; void add(int u,int v,int vi)
{
E[++cnt] = (edge){head[u],v,vi}; head[u] = cnt;
E[++cnt] = (edge){head[v],u,}; head[v] = cnt;
} void Init()
{
scanf("%d%d",&n,&m); cnt = -;
int u,v,vi;
memset(head,-,sizeof(head));
for(int i = ; i <= m; ++i)
{
scanf("%d%d%d",&u,&v,&vi);
add(u,v,vi);
}
} bool bfs()
{
memset(dis,-,sizeof(dis));
Q.push(); dis[] = ;
while(!Q.empty())
{
int u = Q.front(); Q.pop();
for(int i = head[u]; ~i; i = E[i].nxt)
{
int v = E[i].to;
if(dis[v] == - && E[i].vi > ) dis[v] = dis[u] + , Q.push(v);
}
}
return (dis[n] > );
} int dfs(int u,int t,int ff)
{
int ret = , cost = ;
if(u == t) return ff;
for(int i = cur[u] ; ~i; i = E[i].nxt)
{
int v = E[i].to;
if(dis[v] != dis[u] + ) continue;
cost = dfs(v,t,min(ff-ret,E[i].vi));
E[i].vi -= cost, E[i^].vi += cost; ret += cost;
if(E[i].vi) cur[u] = i;
if(ret == ff) return ff;
}
if(!ret) dis[u] = -;
return ret;
} int max_flow(int s,int t)
{
int ret = ;
while(bfs())
{
for(int i = ; i <= n; ++i) cur[i] = head[i];
ret += dfs(s,t,inf);
}
return ret;
} void Solve()
{
int ans = max_flow(,n);
printf("%d\n",ans);
} int main()
{
Init();
Solve(); return ;
}

最大流加强 dinic+当前弧优化的更多相关文章

  1. ARC085E(最小割规划【最大流】,Dinic当前弧优化)

    #include<bits/stdc++.h>using namespace std;typedef long long ll;const ll inf=0x3f3f3f3f;int cn ...

  2. P3376 网络流-最大流模板题(Dinic&plus;当前弧优化)

    (点击此处查看原题) Dinic算法 Dinic算法相对于EK算法,主要区别在于Dinic算法对图实现了分层,使得我们可以用一次bfs,一次dfs使得多条增广路得到增广 普通的Dinic算法已经可以处 ...

  3. &lbrack;Poj2112&rsqb;&lbrack;USACO2003 US OPEN&rsqb; Optimal Milking &lbrack;网络流,最大流&rsqb;&lbrack;Dinic&plus;当前弧优化&rsqb;

    题意:有K个挤奶机编号1~K,有C只奶牛编号(K+1)~(C+K),每个挤奶机之多能挤M头牛,现在让奶牛走到挤奶机处,求奶牛所走的最长的一条边至少是多少. 题解:从起点向挤奶机连边,容量为M,从挤奶机 ...

  4. Dinic当前弧优化 模板及教程

    在阅读本文前,建议先自学最大流的Ek算法. 引入 Ek的核心是执行bfs,一旦找到增广路就停下来进行增广.换言之,执行一遍BFS执行一遍DFS,这使得效率大大降低.于是我们可以考虑优化. 核心思路 在 ...

  5. 网络最大流算法—Dinic算法及优化

    前置知识 网络最大流入门 前言 Dinic在信息学奥赛中是一种最常用的求网络最大流的算法. 它凭借着思路直观,代码难度小,性能优越等优势,深受广大oier青睐 思想 $Dinic$算法属于增广路算法. ...

  6. HDU 4280 Island Transport(dinic&plus;当前弧优化)

    Island Transport Description In the vast waters far far away, there are many islands. People are liv ...

  7. 【Luogu】P1231教辅的组成(拆点&plus;Dinic&plus;当前弧优化)

    题目链接 妈耶 我的图建反了两次 准确的说是有两个地方建反了,然后反上加反改了一个小时…… 知道为什么要拆点吗? 假设这是你的图   左边到右边依次是超级源点    练习册     书     答案 ...

  8. 网络流小记&lpar;EK&amp&semi;dinic&amp&semi;当前弧优化&amp&semi;费用流&rpar;

    欢 迎 来 到 网 络 瘤 的 世 界 什么是网络流? 现在我们有一座水库,周围有n个村庄,每个村庄都需要水,所以会修水管(每个水管都有一定的容量,流过的水量不能超过容量).最终水一定会流向唯一一个废 ...

  9. 网络流 - dinic &plus; 当前弧优化【代码】

    这是初学网络流的时候从<算法竞赛进阶指南>抄下来的一份代码,自己理解的也不是很透彻. 注意,边要从 \(1\) 开始计,不然直接 \(xor\) 运算的话取反边会直接炸掉. #includ ...

随机推荐

  1. 在eclipse中部署jsp项目

    昨天在做实验的时候发现图片的路径不对,怎么改都不对,后来想到在浏览器中输入localhost:8080是tomcat服务器的路径,没找到资源是不是就是项没有部署到tomcat中,去tomcat的web ...

  2. 标签的innerHTML属性和html&lpar;&rpar;

    在新公司开发编码的时候,经常写js代码:有时候就需要往某个标签里添加一些html脚本或者要拿到某个标签里的html脚本,那么就会用到innerHTML和html. 1.innerHTML属性 w3sc ...

  3. 深拷贝与浅拷贝&lpar;mutableCopy与Copy&rpar;详解 iOS

    深拷贝与浅拷贝(mutableCopy与Copy)详解 iOS ios中并不是所有的对象都支持copy,mutableCopy,遵守NSCopying 协议的类可以发送copy消息,遵守NSMutab ...

  4. Pig Apache Hadoop

    http://blog.cloudera.com/blog/2009/06/analyzing-apache-logs-with-pig/

  5. Havel定理

    先贴一个百度百科的注释 Havel定理编辑 本词条缺少概述.名片图,补充相关内容使词条更完整,还能快速升级,赶紧来编辑吧! 中文名 Havel定理 外文名 Canisters theorem 特    ...

  6. 输出一个string的所有排列情况

    问题: 1.加入输入是{a,b,c}; 2.输出abc,acb,bac,bca,cab,cba; 代码描述: 1.递归遍历所有情况 2.方法FUN输入为:要排列的字符串char inp[];inp[] ...

  7. setTimeout传参 和 运行机制

    1.setTimeout 传参数 setTimeout还允许添加更多的参数.它们将被传入推迟执行的函数(回调函数) 上面代码中,setTimeout共有4个参数.最后那两个参数,将在1000毫秒之后回 ...

  8. Python开发【第十一篇】:MySQL

    数据库介绍 数据库(Database)是按照数据结构来组织.存储和管理数据的仓库.每个数据库都有一个或多个不同的API用于创建.访问.管理.搜索和复制所保存的数据.每个数据库都有一个或多个不同的API ...

  9. 非root用户如何使用docker命令

    docker命令默认只能root使用的,但我们可以赋权给其他用户,使用时先照常新建用户: [root@10 ~]# useradd docker [root@10 ~]# passwd docker ...

  10. PHP进阶-浏览器到PHP发展历史

    从浏览器到PHP发展历史 php-cgi实现cgi的解析器,每个fork过程都开启一个进程,并会进行一个关闭进程的操作. 长注内存解释器(一个进程) fastcgi 多进程共享一个端口是一个问题,多进 ...