最近在为比赛恶补网络流..
看学长题单经常看自闭了www
#include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; const int maxn=100010; bool vis[maxn]; int n,m,s,t,x,y,z,f,dis[maxn],pre[maxn],last[maxn],flow[maxn],maxflow,mincost; //dis最小花费;pre每个点的前驱;last每个点的所连的前一条边;flow源点到此处的流量 struct Edge{ int to,next,flow,dis;//flow流量 dis花费 }edge[maxn]; int head[maxn],num_edge; queue <int> q; void add_edge(int from,int to,int flow,int dis) { edge[++num_edge].next=head[from]; edge[num_edge].to=to; edge[num_edge].flow=flow; edge[num_edge].dis=dis; head[from]=num_edge; } bool spfa(int s,int t) { memset(dis,0x7f,sizeof(dis)); memset(flow,0x7f,sizeof(flow)); memset(vis,0,sizeof(vis)); q.push(s); vis[s]=1; dis[s]=0; pre[t]=-1; while (!q.empty()) { int now=q.front(); q.pop(); vis[now]=0; for (int i=head[now]; i!=-1; i=edge[i].next) { if (edge[i].flow>0 && dis[edge[i].to]>dis[now]+edge[i].dis)//正边 { dis[edge[i].to]=dis[now]+edge[i].dis; pre[edge[i].to]=now; last[edge[i].to]=i; flow[edge[i].to]=min(flow[now],edge[i].flow);// if (!vis[edge[i].to]) { vis[edge[i].to]=1; q.push(edge[i].to); } } } } return pre[t]!=-1; } void MCMF() { while (spfa(s,t)) { int now=t; maxflow+=flow[t]; mincost+=flow[t]*dis[t]; while (now!=s) {//从源点一直回溯到汇点 edge[last[now]].flow-=flow[t];//flow和dis容易搞混 edge[last[now]^1].flow+=flow[t]; now=pre[now]; } } } int main() { memset(head,-1,sizeof(head)); num_edge=-1;//初始化 scanf("%d%d%d%d",&n,&m,&s,&t); for (int i=1; i<=m; i++) { scanf("%d%d%d%d",&x,&y,&z,&f); add_edge(x,y,z,f); add_edge(y,x,0,-f); //反边的流量为0,花费是相反数 } MCMF(); printf("%d %d",maxflow,mincost); return 0; }
原文地址:http://www.cnblogs.com/liyishui2003/p/16811372.html
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,请务用于商业用途!
3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员!
8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载
声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性