hdu - 3549 Flow Problem (最大流模板题)

时间:2023-02-24 12:57:12

http://acm.hdu.edu.cn/showproblem.php?pid=3549

Ford-Fulkerson算法.

#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>
#include <algorithm>
#include <string>
#include <set>
#include <functional>
#include <numeric>
#include <sstream>
#include <stack>
#include <map>
#include <queue>
#pragma comment(linker, "/STACK:102400000,102400000")
#define CL(arr, val) memset(arr, val, sizeof(arr)) #define ll long long
#define inf 0x7f7f7f7f
#define lc l,m,rt<<1
#define rc m + 1,r,rt<<1|1
#define pi acos(-1.0) #define L(x) (x) << 1
#define R(x) (x) << 1 | 1
#define MID(l, r) (l + r) >> 1
#define Min(x, y) (x) < (y) ? (x) : (y)
#define Max(x, y) (x) < (y) ? (y) : (x)
#define E(x) (1 << (x))
#define iabs(x) (x) < 0 ? -(x) : (x)
#define OUT(x) printf("%I64d\n", x)
#define lowbit(x) (x)&(-x)
#define Read() freopen("a.txt", "r", stdin)
#define Write() freopen("b.txt", "w", stdout);
#define maxn 1010
#define maxv 1010
#define mod 1000000000
using namespace std; struct edge
{
int to,cap,rev;
edge(){}
edge(int x,int y,int z)
{
to=x;
cap=y;
rev=z;
}
}; vector<edge>G[maxv];
bool used[maxv]; void add_edge(int from,int to,int cap)
{
G[from].push_back((edge){to,cap,G[to].size()});
G[to].push_back((edge){from,,G[from].size()-});
} int dfs(int v,int t,int f)
{
if(v==t) return f;
used[v]=true;
for(int i=;i<G[v].size();i++)
{
edge &e=G[v][i];
if(!used[e.to]&&e.cap>)
{
int d=dfs(e.to,t,min(f,e.cap));
if(d>)
{
e.cap-=d;
G[e.to][e.rev].cap+=d;
// printf("%d %d\n",e.to,e.rev);
return d;
}
}
}
return ;
} int max_flow(int s,int t)
{
int flow=;
for(;;)
{
memset(used,,sizeof(used));
int f=dfs(s,t,inf);
if(f==) return flow;
flow+=f;
}
}
int main()
{
//freopen("a.txt","r",stdin);
int t,n,m,a,b,c,j=;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
G[i].clear();
for(int i=;i<m;i++)
{
scanf("%d%d%d",&a,&b,&c);
add_edge(a,b,c);
}
printf("Case %d: %d\n",j++,max_flow(,n));
}
return ;
}

Dinic算法:(动态邻接表)

 #include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>
#include <algorithm>
#include <string>
#include <set>
#include <functional>
#include <numeric>
#include <sstream>
#include <stack>
#include <map>
#include <queue>
#pragma comment(linker, "/STACK:102400000,102400000")
#define CL(arr, val) memset(arr, val, sizeof(arr)) #define ll long long
#define inf 0x7f7f7f7f
#define lc l,m,rt<<1
#define rc m + 1,r,rt<<1|1
#define pi acos(-1.0) #define L(x) (x) << 1
#define R(x) (x) << 1 | 1
#define MID(l, r) (l + r) >> 1
#define Min(x, y) (x) < (y) ? (x) : (y)
#define Max(x, y) (x) < (y) ? (y) : (x)
#define E(x) (1 << (x))
#define iabs(x) (x) < 0 ? -(x) : (x)
#define OUT(x) printf("%I64d\n", x)
#define lowbit(x) (x)&(-x)
#define Read() freopen("a.txt", "r", stdin)
#define Write() freopen("b.txt", "w", stdout);
#define maxn 1010
#define maxv 1010
#define mod 1000000000
using namespace std; struct edge
{
int to,cap,rev;
edge(){}
edge(int x,int y,int z)
{
to=x;
cap=y;
rev=z;
}
}; vector<edge>G[maxv];
int level[maxv];
int iter[maxv]; void add_edge(int from,int to,int cap)
{
G[from].push_back((edge){to,cap,G[to].size()});
G[to].push_back((edge){from,,G[from].size()-});
} void bfs(int s)
{
memset(level,-,sizeof(level));
queue<int>que;
level[s]=;
que.push(s);
while(!que.empty())
{
int v=que.front();que.pop();
for(int i=;i<G[v].size();i++)
{
edge &e=G[v][i];
if(e.cap>&&level[e.to]<)
{
level[e.to]=level[v]+;
que.push(e.to);
}
}
}
}
int dfs(int v,int t,int f)
{
if(v==t) return f;
for(int &i=iter[v];i<G[v].size();i++)
{
edge &e=G[v][i];
if(e.cap>&&level[v]<level[e.to])
{
int d=dfs(e.to,t,min(f,e.cap));
if(d>)
{
e.cap-=d;
G[e.to][e.rev].cap+=d;
// printf("%d %d %d\n",e.to,e.rev,G[e.to][e.rev]);
return d;
}
}
}
return ;
} int max_flow(int s,int t)
{
int flow=;
for(;;)
{
bfs(s);
if(level[t]<) return flow;
memset(iter,,sizeof(iter));
int f;
while((f=dfs(s,t,inf))>)
flow+=f;
}
}
int main()
{
//freopen("a.txt","r",stdin);
int t,n,m,a,b,c,j=;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
G[i].clear();
for(int i=;i<m;i++)
{
scanf("%d%d%d",&a,&b,&c);
add_edge(a,b,c);
}
printf("Case %d: %d\n",j++,max_flow(,n));
}
return ;
}

hdu - 3549 Flow Problem (最大流模板题)的更多相关文章

  1. hdu 3549 Flow Problem 最大流问题 (模板题)

    Flow Problem Time Limit: 5000/5000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others)Tota ...

  2. hdu 3549 Flow Problem &lpar;最大流&rpar;

    裸最大流,做模板用 m条边,n个点,求最大流 #include <iostream> #include <cstdio> #include <cstring> #i ...

  3. &lbrack;hdu3549&rsqb;Flow Problem&lpar;最大流模板题&rpar;

    解题关键:使用的挑战程序设计竞赛上的模板,第一道网络流题目,效率比较低,且用不习惯的vector来建图. 看到网上其他人说此题有重边,需要注意下,此问题只在邻接矩阵建图时会出问题,邻接表不会存在的,也 ...

  4. hdu 3549 Flow Problem 最大流 Dinic

    题目链接 题意 裸的最大流. 学习参考 http://www.cnblogs.com/SYCstudio/p/7260613.html Code #include <bits/stdc++.h& ...

  5. HDU 3549 Flow Problem(最大流)

    HDU 3549 Flow Problem(最大流) Time Limit: 5000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/ ...

  6. 网络流 HDU 3549 Flow Problem

    网络流 HDU 3549 Flow Problem 题目:pid=3549">http://acm.hdu.edu.cn/showproblem.php?pid=3549 用增广路算法 ...

  7. hdu 3549 Flow Problem【最大流增广路入门模板题】

    题目:http://acm.hdu.edu.cn/showproblem.php?pid=3549 Flow Problem Time Limit: 5000/5000 MS (Java/Others ...

  8. hdu 3549 Flow Problem

    题目连接 http://acm.hdu.edu.cn/showproblem.php?pid=3549 Flow Problem Description Network flow is a well- ...

  9. HDU 3549 Flow Problem(最大流模板)

    http://acm.hdu.edu.cn/showproblem.php?pid=3549 刚接触网络流,感觉有点难啊,只好先拿几道基础的模板题来练练手. 最大流的模板题. #include< ...

随机推荐

  1. ABAP 生产订单的创建与修改函数

    ABAP 生产订单的创建与修改函数转自http://www.cnblogs.com/aBaoRong/archive/2012/04/11/2441946.html   如果生产订单过多,可以批量创建 ...

  2. mysql 如何设置自动增长序列 sequence&lpar;一&rpar;

    背景:由于项目需要,必须用mysql设置主键自增长,而且想用字符串的.经过上网查找并且实验,终于做出了一套方案.现在就共享给大家! 解决思路:由于mysql不带sequence,所以要手写的,创建一张 ...

  3. git 给远程库 添加多个url地址

     目录[-] 前提 使用流程 原理解析 注意 Other 参考文章 作者:shede333主页:http://my.oschina.net/shede333 && http://blo ...

  4. 【Java】从域名得到ip

    package sdfg; import java.net.InetAddress; //import java.net.UnknownHostException; import java.io.*; ...

  5. DropdownList绑定的两种方法

    动态绑定方法一:动态绑定数据库中的字段. SqlConnection conn = UtilitySqlClass.OperateDataBase.ReturnConn();string strSQL ...

  6. AJAX安全-Session做Token

    个人思路,请大神看到了指点 个人理解token是防止扫号机或者恶意注册.恶意发表灌水,有些JS写的token算法,也会被抓出来被利用,个人感觉还是用会过期的Session做token更好,服务器存储, ...

  7. xml解析,练习

    <collection shelf="New Arrivals"><movie title="Enemy Behind">   < ...

  8. js、jq事件绑定方式总结——以click事件为例

    一.JavaScript点击事件绑定方法 1.1 HTML onclick事件属性 <button onclick="clickMe(this)">click me&l ...

  9. 数据库查询的数据导出到xls表,集合数据导出到xls表

    //实体类package com.outxls; public class Student { private Integer studentId; private String studentNam ...

  10. Spring 注解详细分析解释有实例

    概述 注释配置相对于 XML 配置具有很多的优势: 它可以充分利用 Java 的反射机制获取类结构信息,这些信息可以有效减少配置的工作.如使用 JPA 注释配置 ORM 映射时,我们就不需要指定 PO ...