http://poj.org/problem?id=1459
题意:有一个电路网络,每个节点可以产生、传递、消耗若干电量,有点线连接结点,每个电线有最大传输量,求这个网络的最大消费量。
思路:从源点到发电站连边,流量为发电量,从用户到汇点连边,流量为消费量,再根据电线连双向边,求最大流即可。
#include<stdio.h>
#include<string.h>
#include<queue>
const int N=;
const int INF=<<;
using namespace std;
int map[N][N];
int pre[N];
int n,np,nc,m; int bfs(int s,int d)
{
queue<int>q;
memset(pre,-,sizeof(pre));
pre[s] = ;
int k;
q.push(s);
while(!q.empty())
{
k = q.front();
q.pop();
for (int i = ; i <= n+; i ++)
{
if (pre[i]==- && map[k][i] > )
{
pre[i] = k;
if (i==d)
return ;
q.push(i);
}
}
}
return ;
}
int maxflow(int s,int d)
{
int maxf = ;
while(bfs(s,d))
{
int minf = INF;
for (int i = d; i!=s; i = pre[i])
//minf = minf < map[pre[i]][i] ? minf:map[pre[i]][i];
minf = min(minf,map[pre[i]][i]);
for (int i = d; i!=s; i = pre[i])
{
map[pre[i]][i] -= minf;
map[i][pre[i]] += minf;
}
maxf += minf;
}
return maxf;
}
int main()
{
int s,d;
int u,v,w;
char str[];
while(~scanf("%d%d%d%d",&n,&np,&nc,&m))
{
memset(map,,sizeof(map));
s = n;
d = n+;
for (int i = ; i < m; i ++)
{
scanf("%s",str);
sscanf(str,"(%d,%d)%d",&u,&v,&w);
map[u][v] = w; }
for (int i = ; i < np; i ++)
{
scanf("%s",str);
sscanf(str,"(%d)%d",&v,&w);
map[s][v] = w;
}
for (int i = ; i < nc; i ++)
{
scanf("%s",str);
sscanf(str,"(%d)%d",&u,&w);
map[u][d] = w;
}
printf("%d\n",maxflow(s,d));
}
return ;
}
Power Network(最大流(EK算法))的更多相关文章
-
poj1459 Power Network --- 最大流 EK/dinic
求从电站->调度站->消费者的最大流,给出一些边上的容量.和电站和消费者能够输入和输出的最大量. 加入一个超级源点和汇点,建边跑模板就能够了. 两个模板逗能够. #include < ...
-
POJ 1459 Power Network 最大流(Edmonds_Karp算法)
题目链接: http://poj.org/problem?id=1459 因为发电站有多个,所以需要一个超级源点,消费者有多个,需要一个超级汇点,这样超级源点到发电站的权值就是发电站的容量,也就是题目 ...
-
POJ-1459(最大流+EK算法)
Power Network POJ-1459 这题值得思索的就是特殊的输入,如何输入一连串字符.这里采用的方法是根据输入已知的输入格式,事先预定好要接受的数据类型. 这里套用的板子也是最大流的模板,但 ...
-
最大流EK算法/DINIC算法学习
之前一直觉得很难,没学过网络流,毕竟是基础知识现在重新来看. 定义一下网络流问题,就是在一幅有向图中,每条边有两个属性,一个是cap表示容量,一个是flow 表示流过的流量.我们要求解的问题就是从S点 ...
-
二分图的最大匹配——最大流EK算法
序: 既然是个图,并且求边数的最大值.那么这就可以转化为网络流的求最大流问题. 只需要将源点与其中一子集的所有节点相连,汇点与另一子集的所有节点相连,将所有弧的流量限制置为1,那么最大流 == 最大匹 ...
-
最大流——EK算法
一.算法理论 [基本思想] 反复寻找源点s到汇点t之间的增广路径,若有,找出增广路径上每一段[容量-流量]的最小值delta,若无,则结束.在寻找增广路径时,可以用BFS来找,并且更新残留网络的值(涉 ...
-
(通俗易懂小白入门)网络流最大流——EK算法
网络流 网络流是模仿水流解决生活中类似问题的一种方法策略,来看这么一个问题,有一个自来水厂S,它要向目标T提供水量,从S出发有不确定数量和方向的水管,它可能直接到达T或者经过更多的节点的中转,目前确定 ...
-
vector实现最大流EK算法
序: 在之前的文章中实现了不利用STL实现EK算法,效率也较高.这次我们企图简化代码,减少变量的使用与手写模拟的代码. 注意:vector等STL的container在不开O2优化的时候实现同一个效果 ...
-
POJ1459 Power Network —— 最大流
题目链接:https://vjudge.net/problem/POJ-1459 Power Network Time Limit: 2000MS Memory Limit: 32768K Tot ...
随机推荐
-
MD5实现32位加密
好记性不如烂笔头,随手记记 附代码 public static void Main(string[] args) { Console.WriteLine("长度为" + UseMd ...
-
C语言:链表实现的一个实例
问题:写一个程序输入你一年看过的所有电影以及每部电影的各种信息(简化问题:每部电影只要求输入片名和评价) 链表实现: #include<stdio.h> #include<stdli ...
-
破解ZIP加密文件密码fcrackzip
破解ZIP加密文件密码fcrackzip ZIP是最常见的文件压缩方式.由于其压缩算法开源,主流操作系统都支持这种压缩算法.ZIP压缩方式支持密码加密.加密的时候会在文件头部保存密钥相关信息.利用这个 ...
-
3.C#中的多重委托
阅读目录 一:多重委托概述 二:多重委托实例 一:多重委托概述 1.委托的调用其实是一个调用列表,可以同时调用多个不同的方法 2.第1个委托加上第2个委托赋予第3个委托,相当于把两个方法按顺 ...
-
easyui + jdbc 实现简单的数据库管理。
/** * 分页未完成 ,执行sql 查询 与 更新未完成. * 代码拿去,有同学完成了可以再分享出来. * 代码稍微有些乱,没时间整理. * 暂时仅支持oracle ,因sql语句黏合度太高. * ...
-
Yii Framework 开发教程Zii组件-Tabs示例
有关Yii Tab类: http://www.yiichina.com/api/CTabView http://www.yiichina.com/api/CJuiTabs http://blog.cs ...
-
深入浅出Node.js (10) - 测试
10.1 单元测试 10.1.1 单元测试的意义 10.1.2 单元测试介绍 10.1.3 工程化与自动化 10.1.4 小结 10.2 性能测试 10.2.1 基准测试 10.2.2 压力测试 10 ...
-
java线程并发控制:ReentrantLock Condition使用详解
本文摘自:http://outofmemory.cn/java/java.util.concurrent/lock-reentrantlock-condition java的java.util.con ...
-
poj2635The Embarrassed Cryptographer(同余膜定理)
The Embarrassed Cryptographer Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 15069 A ...
-
本地工程引入maven工程的配置方式
一.准备 IDE: IntelliJ IDEA 2016.3.1 maven: 3.5.2 JDK: 1.8 操作系统: Window 7 二.配置 1. maven 3.5 下载地址:http:// ...