网络流算法

  • c9998118
    了解作者
  • C/C++
    开发工具
  • 1.2KB
    文件大小
  • zip
    文件格式
  • 0
    收藏次数
  • 1 积分
    下载积分
  • 0
    下载次数
  • 2022-05-25 14:05
    上传日期
网络流算法,给想学习的同学作为参考。实现略显粗糙,见谅
Ans8.zip
  • Ans8.cpp
    2.5KB
内容介绍
#include<cstdio> #include<algorithm rel='nofollow' onclick='return false;'> #include<cstring> #include<iostream> #include<map> #include<set> #include<bitset> #include<vector> #include<cmath> #define N 505 #define M 1000005 #define K 18 #define ls (t<<1) #define rs ((t<<1)|1) #define mid ((l+r)>>1) #define fi first #define se second #define pb push_back #define Mo 1000000007 using namespace std; int read() { int x,f=0; char c; while (c=getchar(),c<'0'||c>'9'); if (c=='-') f=1,c=getchar(); x=c-'0'; while (c=getchar(),c>='0'&&c<='9') x=(x<<1)+(x<<3)+c-'0'; return f?-x:x; } struct Node{ int flow,ed,before; }s[M]; int i,j,m,n,p,k,k1,fox[N*3],S; struct Bian{ int x,y,z; }B[M]; int a[N],b[N],st,ed; void add(int x,int y,int flow) { s[++k1].ed=y; s[k1].before=fox[x]; fox[x]=k1; s[k1].flow=flow; s[++k1].ed=x; s[k1].before=fox[y]; fox[y]=k1; s[k1].flow=0; } const int inf=(int)1e9; int dis[N*3],Q[N*3],fa[N*3]; int bfs(int x) { int i,l; Q[Q[0]=1]=x; memset(dis,-1,sizeof(dis)); dis[st]=0; for (l=1;l<=Q[0]&&dis[ed]==-1;++l) { int p=Q[l]; for (i=fox[p];i;i=s[i].before) if (s[i].flow) { int k=s[i].ed; if (dis[k]==-1) dis[k]=dis[p]+1,Q[++Q[0]]=k,fa[k]=i; } } return dis[ed]!=-1; } int dfs(int x,int flow) { int i,a,nowans=0; if (x==ed) return flow; for (i=fox[x];i&&flow;i=s[i].before) if (s[i].flow) { int p=s[i].ed; if (dis[p]==dis[x]+1) { a=dfs(p,min(flow,s[i].flow)); s[i].flow-=a; s[i^1].flow+=a; flow-=a; nowans+=a; } } if (!nowans) dis[x]=-1; return nowans; } int maxflow() { int i,ans=0; while (bfs(st)) ans+=dfs(st,inf); return ans; } int cmp(Bian a,Bian b) { if (a.x!=b.x) return a.x<b.x; return a.y<b.y; } void Main() { k1=1; memset(fox,0,sizeof(fox)); scanf("%d%d%d",&n,&m,&S); for (i=1;i<=m;++i) B[i].x=read(),B[i].y=read(),B[i].z=read(); for (i=1;i<=n;++i) a[i]=read(); for (i=1;i<=n;++i) b[i]=read(); st=3*n+1; ed=st+1; for (i=1;i<=n;++i) { add(i,i+n,b[i]); add(i+n,i+2*n,a[i]); add(i+2*n,ed,inf); } // sort(B+1,B+m+1,cmp); for (i=1;i<=m;i++) add(B[i].y+n,B[i].x,B[i].z); add(st,S,inf); printf("%d\n",maxflow()); } int main() { // freopen("1.in","r",stdin); int T; scanf("%d",&T); for (;T--;) Main(); } /* 1 5 5 5 1 2 5 1 3 5 2 4 8 4 5 10 3 5 15 100 100 100 200 200 3 5 7 9 1000000 */
评论
    相关推荐
    • 最大网络流Dinic算法
      用于计算最大网络流的经典的Dinic算法,代码自带例子,边权支持double类型。
    • 网络流相关论文
      《最小割模型在信息学竞赛中的应用》 ...《从一套题目的解法试谈网络流的构造与算法》 《浅谈网络流算法的应用》 《最大流在信息学竞赛中应用的一个模型》 《一种简易的方法求解流量有上下界的网络中网络流问题》
    • 网络流资料
      这是关于ACM 相关的 网络流 算法资料。
    • dinic网络流算法
      本文是dinic网络流算法的源程序,是一套模板,经过本人测试,适合参加ACM的同志!
    • 网络流算法
      网络流算法的介绍,分析
    • 最大网络流ISAP算法
      用于计算最大网络流的经典的ISAP算法,代码自带例子,边权支持double类型。
    • 网络流24题题解
      包含网络流24题算法的全部详细题解 每题附带完整程序 (注意:没有数据包 请到其他地方下载
    • 网络流算法
      网络流算法的详细讲解,希望能帮助到需要的人~
    • 网络流最大流.rar
      网络流最大流的一些经典问题和求解方法,多多支持
    • libiconv-1.1.tar.gz
      字符集转换程序