专门做装修的网站有哪些,重庆做网站哪家好,ui设计是什么部门,网站建设分金手指排名二六文章目录1.网络最大流题目描述解析反悔边分层#xff08;避免环流#xff09;时间优化代码2.费用流描述解析代码1.网络最大流
洛谷P3376
题目描述 给出一个网络图#xff0c;以及其源点和汇点#xff0c;求出其网络最大流。
解析
网络流的思想就是在原有的基础上不断进…
文章目录1.网络最大流题目描述解析反悔边分层避免环流时间优化代码2.费用流描述解析代码1.网络最大流
洛谷P3376
题目描述 给出一个网络图以及其源点和汇点求出其网络最大流。
解析
网络流的思想就是在原有的基础上不断进行增广 基于一个贪心的思路先bfs判断是否存在增广路再通过dfs增广
反悔边
但显然贪心会出错比如当前终点通过其他点来使用会更优时 所以就引入了反悔边 就是与所给边方向相反一开始容量为0 增广使用边时除了把改变的边容量减去流量再把反向边加上同样的流量即可 这样以后在必要时就可以通过走反悔边的方式撤销之前的错误决策 举个例子 从S到T 如果贪心的走。先让2的10给了4 但实际上应该是2给5,3给4最优 那么我们就在2给4时使4到2的边容量从0加到10 这样在计算3这个点时就会顺着1-3-4-2-5-T走到终点 2-4与4-2流量都为10等价于把一开始2到4这步操作撤销了
分层避免环流
为了避免dfs环流死循环的情况我们要把这个图先分一下层 比如上图就是 1层S 2层2 3 3层4 5 4层 T 强制让dfs只能走到层数1的点
时间优化
只是这么写的话会T掉一个点也可能是我太菜常数太大。。。 考虑能否优化
我们发现每次bfs之后的多次dfs增广中这个图的分层结构是固定的 每个点尝试走的出边可能有一些在之前几次dfs已经用过再枚举时其实已经得不到更多的流了 所以我们每次dfs时到每一个点就从上次dfs枚举到的出边开始枚举就行了 但注意重新bfs后图的结构改变之前没用的边可能又能有流了 所以要重新从头枚举
代码
#includebits/stdc.h
using namespace std;
#define ll long long
const int N300;
const int M15500;struct node{int to,nxt;ll cap;
}p[M];
int fi[N],cnt-1;
void addline(int x,int y,ll v){p[cnt](node){y,fi[x],v};fi[x]cnt;
}int n,m,s,t;
int a,b,c,d;int dis[N];
int cur[N];
void print(){for(int i1;in;i) printf(%d ,dis[i]);printf(\n);}
int bfs(){queueintq;q.push(s);memset(dis,0,sizeof(dis));dis[s]1;while (!q.empty()){int x q.front();q.pop();for (int i cur[x] fi[x];~i;i p[i].nxt){int to p[i].to;if (dis[to]||!p[i].cap) continue;dis[to] dis[x] 1;q.push(to);}}return dis[t];
}
ll dfs(int x,ll lim){if(xt||!lim) return lim;
// printf(%d\n,x);ll res0;for(int icur[x];~ilim;ip[i].nxt){int top[i].to;if(dis[to]!dis[x]1) continue;ll fdfs(to,min(p[i].cap,lim));lim-f;resf;p[i].cap-f;p[i^1].capf;}return res;
}
ll dinic(){ll ans0,flow;while(bfs()){while(flowdfs(s,2e15)) ansflow;}return ans;
}
int main(){memset(fi,-1,sizeof(fi));scanf(%d%d,m,n);s1;tn;for(int i1;im;i){scanf(%d%d%d,a,b,c);addline(a,b,c);addline(b,a,0);}printf(%lld,dinic());
}
/*
4 5 4 3
4 2 30
4 3 20
2 3 20
2 1 30
1 3 40
*/2.费用流
洛谷P3381
描述
和最大流类似 只是每条边加了一个单位流的费用 求在最大流的前提下的最小费用方案
解析
上一题搞完这题就好多了 由于要求最小费用把增广的bfs改为spfa跑费用的最短路 更新时记录路径 寻找路径上流量最小的值 然后累加费用即可
代码
#includebits/stdc.h
using namespace std;
#define ll long long
const int N5500;
const int M55000;struct node{int to,nxt;ll cap,v;
}p[M1];
int fi[N],cnt-1;
void addline(int x,int y,ll w,ll v){p[cnt](node){y,fi[x],w,v};fi[x]cnt;
}int n,m,s,t;
int a,b,c,d;int dis[N];
int pre[N],from[N];
int vis[N];
bool spfa(){pre[t]0;memset(dis,63,sizeof(dis));memset(vis,0,sizeof(vis));queueintq;q.push(s);vis[s]1;dis[s]0;while(!q.empty()){int nowq.front();q.pop();vis[now]0;
// printf(now%d);for(int ifi[now];~i;ip[i].nxt){int top[i].to;if(p[i].cap0) continue;if(dis[to]dis[now]p[i].v){dis[to]dis[now]p[i].v;pre[to]now;from[to]i;if(!vis[to]){vis[to]1;q.push(to);}}}}return pre[t];
}
void dinic(){ll flow0,v0,tmp;while(spfa()){tmp2e15;for(int it;i!s;ipre[i]) tmpmin(tmp,p[from[i]].cap);flowtmp;for(int it;i!s;ipre[i]){vtmp*p[from[i]].v;p[from[i]].cap-tmp;p[from[i]^1].captmp;}}printf(%lld %lld,flow,v);return;
}
int main(){memset(fi,-1,sizeof(fi));scanf(%d%d%d%d,n,m,s,t);for(int i1;im;i){scanf(%d%d%d%d,a,b,c,d);addline(a,b,c,d);addline(b,a,0,-d);}dinic();return 0;
}
/*
4 5 4 3
4 2 30
4 3 20
2 3 20
2 1 30
1 3 40
*/
