网络吞吐量(network)
2024-10-07 05:40:25
题目
分析
过一遍spfa，把从点1到其他每一个点的最短路求出来，
接着递归把所有最短路径上的路径保留，其他的删掉。
对于保留的路径作为网络流的边，流量为无穷大，对于每个点拆点两个点之间的流量为吞吐量。
跑个网络流。
#include <fstream>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
const long long maxlongint=2147483647000000;
using namespace std;
long long dis[2100],a[600][600],f[2000][2000],d[600000],tot;
long long v[2100];
long long n,m,id;
long long spfa()
{
long long i,j,l;
dis[1]=0;
d[1]=1;
long long head=0,tail=1,k;
while(head<tail)
{
head++;
k=d[head];
v[k]=true;
for(i=1;i<=n;i++)
{
if(a[k][i]>0)
{
if(a[k][i]+dis[k]<dis[i])
{
dis[i]=dis[k]+a[k][i];
if(v[i])
{
v[i]=false;
d[++tail]=i;
}
}
}
}
}
}
long long dg(long long x,long long v1)
{
if(x==n) return 0;
v[x]=false;
for(long long i=2;i<=n;i++)
{
if(a[x][i]<maxlongint)
if(v1+a[x][i]==dis[i])
{
f[x+n][i]=maxlongint;
if(v[i])
dg(i,dis[i]);
}
}
}
bool bfs()
{
memset(dis,0,sizeof(dis));
long long i,j,l;
d[1]=1;
long long head=0,tail=1,k;
while(head<tail)
{
k=d[++head];
for(i=2;i<=n+n;i++)
{
if(f[k][i]>0 && dis[i]==0)
{
dis[i]=dis[k]+1;
d[++tail]=i;
}
}
}
if(dis[n+n])
return true;
else return false;
}
long long aug(long long x,long long y)
{
if(x==n+n) return y;
long long o;
for(long long i=1;i<=n+n;i++)
{
if(f[x][i]>0 && dis[x]+1==dis[i])
{
o=aug(i,min(y,f[x][i]));
if(o>0)
{
f[x][i]-=o;
f[i][x]+=o;
return o;
}
}
}
return 0;
}
int main()
{
scanf("%lld%lld",&n,&m);
long long i,j,k,l,x,y,z;
for(i=1;i<=n;i++)
{
dis[i]=maxlongint;
for(j=1;j<=n;j++)
{
a[i][j]=maxlongint;
}
}
for(i=1;i<=m;i++)
{
scanf("%lld%lld%lld",&x,&y,&z);
if(x>y)
{
j=x;
x=y;
y=j;
}
if(x==1) a[x][y]=min(a[x][y],z);else
if(y==n) a[x][y]=min(a[x][y],z);else a[y][x]=a[x][y]=min(a[x][y],z);
}
memset(v,true,sizeof(v));
spfa();
memset(v,true,sizeof(v));
memset(f,0,sizeof(f));
dg(1,0);
long long ans,t=99;
memset(v,0,sizeof(v));
for(i=1;i<=n;i++)
{
scanf("%lld",&f[i][i+n]);
if(i==1 || i==n) f[i][i+n]=maxlongint;
}
ans=0;
while(bfs())
{
ans+=aug(1,maxlongint);
}
cout<<ans;
return 0;
}
最新文章
- 利用SCORE法则来总结一次偷懒的单元测试过程
- Android开发学习---使用Intelij idea 13.1 进行android 开发
- 阿里云安装Tomcat
- hdu 2669 Romantic
- 1、android源代码下载及目录分析，和eclipser的跟踪
- PHP裁剪图片并上传完整demo
- phonegap 新窗口 WebView
- CString转换成int CString类相应函数
- Python 多进程
- 字符串相似度算法（编辑距离算法 Levenshtein Distance）
- lua metatable和metamethod元表和元方法
- Android 使用HorizontalScrollView 实现Gallery效果
- 基于 HTML5 WebGL 的 3D 棉花加工监控系统
- Quartus II 中 Verilog 常见警告/错误汇总
- NLP 第7章 文本向量化
- PIVOT 行列相转
- LeetCode 888 Fair Candy Swap 解题报告
- Docker学习笔记之常见 Dockerfile 使用技巧
- KVM虚拟化技术（五）虚拟机管理
- OCSP