给定一张有向图,每条边都有一个容量C和一个扩容费用W。这里扩容费用是指将容量扩大1所需的费用。求:
1、
在不扩容的情况下,1到N的最大流;
2、 将1到N的最大流增加K所需的最小扩容费用。
求出最大流后,残余网络的流量不变,费用改为 0. 对原图的每一条边,对应增加一条流量为 k,费用为 w 的边,再增加一个源,源到 1 的流量为 k,费用为 0。求最小费用最大流,即为第二问答案。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define min(a,b) ( (a)< (b)? (a): (b) )
#define inf 0x7fffffff
int const N= 1010, M= 5010;
int n, m, k, cnt, S, T;
int dist[N][N];
struct Edge{
int flow, cost, adj;
Edge* next;
}tb[M<<2];
Edge* mat[N], *Pre[N];
inline Edge* reserve( Edge* p ){
return tb+ ( (p- tb)^ 1 );
}
inline void add( int u, int v, int c, int w ){
++cnt;
tb[cnt].adj= v; tb[cnt].flow= c; tb[cnt].cost= w;
tb[cnt].next= mat[u]; mat[u]= tb+ cnt;
++cnt;
tb[cnt].adj= u; tb[cnt].flow= 0; tb[cnt].cost= -w;
tb[cnt].next= mat[v]; mat[v]= tb+ cnt;
}
int que[M<<2], ht[N], flag[N], path[N], head, tail;
int bfs(){
que[0]= S; head= 0; tail= 0;
for( int i= 0; i<= n; ++i ) ht[i]= -1; ht[S]= 0;
while( head<= tail ){
int u= que[head++];
for( Edge* p= mat[u]; p; p= p->next )
if( ht[p->adj]== -1 && p->flow ){
ht[p->adj]= ht[u]+ 1;
que[++tail]= p->adj;
}
}
return ht[T]!= -1;
}
int dfs( int u, int flow ){
if( u== T ) return flow;
int tf= 0, f;
for( Edge* p= mat[u]; p; p= p->next )
if( ht[p->adj]== ht[u]+ 1 && p->flow && flow> tf &&
( f= dfs( p->adj, min( p->flow, flow- tf ) ) ) ){
reserve( p )->flow+= f;
p->flow-= f;
tf+= f;
}
if( tf== 0 ) ht[u]= -1;
return tf;
}
int spfa(){
for( int i= 0; i<= n; ++i ) {
ht[i]= inf; flag[i]= 0; }
que[0]= S; head= tail= 0;
path[S]= S; flag[S]= 1; ht[S]= 0;
while( head<= tail ){
int u= que[head++]; flag[u]= 0;
for( Edge* p= mat[u]; p; p= p->next )
if( p->flow && ht[u]+ p->cost< ht[p->adj] ){
ht[p->adj]= ht[u]+ p->cost;
Pre[p->adj]= p; path[p->adj]= u;
if( flag[p->adj]== 0 ){
flag[p->adj]= 1;
que[++tail]= p->adj;
}
}
}
return ht[T]!= inf;
}
int min_cost(){
int res= 0;
while( spfa() ){
int tf= inf, tmp= path[T];
while( tmp!= S ){
tf= min( Pre[tmp]->flow, tf );
tmp= path[tmp];
}
tmp= path[T];
while( tmp!= S ){
Pre[tmp]->flow-= tf;
reserve( Pre[tmp] )->flow+= tf;
tmp= path[tmp];
}
res+= ht[T]* tf;
}
return res;
}
int main(){
while( scanf("%d%d%d",&n,&m,&k)!= EOF ){
int u, v, c, w;
cnt= -1;
for( int i= 0; i<= n+ 1; ++i ) mat[i]= 0;
for( int i= 0; i<= n; ++i )
for( int j= 0; j<= n; ++j ) dist[i][j]= -1;
S= 1; T= n;
for( int i= 0; i< m; ++i ){
scanf("%d%d%d%d", &u, &v, &c, &w );
add( u, v, c, 0 );
dist[u][v]= w;
}
int ans= 0;
while( bfs() ) ans+= dfs( S, 0x7fffffff );
for( int i= 1; i<= n; ++i )
for( int j= 1; j<= n; ++j )
if( dist[i][j]!= -1 ) add( i, j, k, dist[i][j] );
S= T+ 1;
add( S, 1, k, 0 );
int res= min_cost();
printf("%d %d\n", ans, res );
}
return 0;
}
分享到:
相关推荐
network 网络流 network 网络流 network 网络流 network 网络流 network 网络流
单倍型网络图绘制软件NETWORK 5.0,2020年1月18日更新版本。 Network generates evolutionary trees and networks from genetic, linguistic, and other data. Network can then provide age estimates for any ...
network网络应用程序1111111111111111111111111
Jx-NNT : 神经网络工具箱 * 此工具箱包含六种类型的神经网络 + Artificial neural network ( ANN ) + Feed Forward Neural Network ( FFNN ) + Cascade Forward Neural Network ( CFNN ) + Recurrent Neural ...
在Ubuntu Server系统安装完成后默认没有使用network-manager管理网络,此文章简单介绍了如何使用network-manager管理网络。
内容概要:网络售前专家[高级] H3CE-Presales Network (A)模拟题。H3C交换机市场地位。新一代交换机的特征和相关技术介绍。H3C园区网交换机产品介绍。数据中心发展趋势及关注点。H3C数据中心交换机关键技术介绍。H3C...
Network Scanner(局域网IP扫描工具)是一个免费的多线程的IP,NetBIOS和SNMP的扫描仪。其目的是为系统管理员和对计算机安全感兴趣的用户。检测用户自定义的端口并报告已打开的端口,解析主机域名和自动检测您的本地IP...
搬迁神器—网络搬迁工具network_migration_tool.zip
前馈神经网络(Feedforward neural network).pdf 前馈神经网络(Feedforward neural network).pdf 前馈神经网络(Feedforward neural network).pdf 前馈神经网络(Feedforward neural network).pdf 前馈神经网络...
NetWork网络编程TCP和UDP源代码
51Network网络开发板说明书v2.0,入门资料,需要的下载
Microsoft Network Monitor网络协议数据分析工具使用教程.docx
c network C语言网络编程
本资源含多个版本的usb over network,带服务端和客户端,有注册机或注册码。主板版本有usb over network4.5.3,usb over network4.7.3,usb over network4.7.4.usb over network5.0.2等。
1.大致流程 2.频道(NetworkChannel) 3.连接服务器 4.频道辅助器(NetworkChannelHelper) 6.消息头(PacketHe
经典网络编程作品——Unix Network Programming 包括第1卷、第2卷的中英文版本,有需要的请下载 由于附件大小限制,本资源共分为4个部分,文件列表如下: UNIX Network Programming - vol1 ed3 The Sockets ...
NetWork网络测试助手类似于tcpdump。用户通过NetWork网络测试助手,可以查看到网络对应IP中发送的所有网络数据。 NetWork网络测试助手应用于故障修复、分析、软件和协议开发以及教育领域。它具有用户对协议分析器所...
ARCGIS网络分析学习――道路网络分析Network anlysis(详细步骤).pdfARCGIS网络分析学习――道路网络分析Network anlysis(详细步骤).pdfARCGIS网络分析学习――道路网络分析Network anlysis(详细步骤).pdfARCGIS网络...
ARCGIS网络分析学习――道路网络分析Network anlysis(详细步骤).docxARCGIS网络分析学习――道路网络分析Network anlysis(详细步骤).docxARCGIS网络分析学习――道路网络分析Network anlysis(详细步骤).docxARCGIS...
网络Network2 shell perl java sed awk