当前位置:首页 > 云服务器 > 正文内容

网络流(Dinic),嘘......的博客,香港云服务器哪里好

香港256IP千兆站群服务器BGP专线240元起! 华为云香港物理机精品线路全面上线![特价] 企业级CN2 GIA双程专线高速回国 T3机房 香港美国韩国海外独立物理服务器特价热销中!

Dinic详解与实现
(https://www.cnblogs.com/LUO77/p/6115057.html)
(ISAP待留)

struct Dinic{    int c;//cap    int f;//flow}edge[205][205];//i:from; j:to

构造分层网络(level标号)

bool dinic_bfs()//建网{ queue<int>q; memset(level,0,sizeof(level)); q.push(1); level[1]=1; int u,v; while(!q.empty) {  u=q.front();  q.pop();  for(v=1;v<=E;v++)//   if(!level[v]&&edge[u][v].c>edge[u][v].f)   {    level[v]=level[u]+1;    q.push(v);    } } return level[E];//判断E点是否在网络内}

进行增广

int dinic_dfs(int u,int cp)//进行增广 { int tmp=cp; int v,t; if(u==E)//退回原点,增广结束   return cp; for(v=1;v<=E&&tmp;v++)  if(level[u]+1==level[v]&&edge[u][v].c>edge[u][v].f)//符合增广条件   {   t=dinic_dfs(v,min(tmp,edge[u][v].c-edge[u][v].f))//重点理解    edge[u][v].f+=t;//前    edge[v][u].f-=t;// 逆    tmp-=t;//   } return cp-tmp;//tmp减少的总量即增加的流量 }

Dinic主思路

int dinic(){ int sum=0,tf=0; while(dinic_bfs())//判断是否可构造层次网络  {  while(tf=dinic_dfs(1,INF))//进行增广    sum+=tf; } return sum;}

但即便知道了最基本的思路,遇到实际问题依旧很难解决,所以需要对应题目的训练
基本版子
详解来源(https://www.cnblogs.com/TreeDream/p/5866347.html)

#include<iostream>#include<cstring>#include<queue>using namespace std;const int INF=0x3f3f3f3f;const int maxn=505;struct Edge{ int from;int to;int cap;int flow;};struct Dinic{ int n,m,s,t; vector<Edge>edge;vector<int>G[maxn]; int level[maxn],cur[maxn];bool vis[maxn]; void addEdge(int from,int to,int cap) {  edge.push_back((Edge){from,to,cap,0});  edge.push_back((Edge){to,from,0,0});  int m=edge.size();  G[from].push_back(m-2);  G[to].push_back(m-1); }  bool BFS() {  memset(vis,0,sizeof(vis));  queue<int>Q;  Q.push(s);level[s]=0;vis[s]=1;  while(!Q.empty())  {   int x=Q.front();Q.pop();   for(int i=0;i<G[x].size();i++)   {    Edge&e=edge[G[x][i]];  if(!vis[e.to]&&e.cap>e.flow)  {   vis[e.to]=1;level[e.to]=level[x]+1;Q.push(e.to);   }  }  }  return vis[t]; } int DFS(int x,int a) {  if(x==t||a==0) return a;  int flow=0,f;  for(int &i=cur[x];i<G[x].size();i++)  {    Edge&e=edge[G[x][i]];    if(level[e.to]==level[x]+1&&(f=DFS(e.to,min(a,e.cap-e.flow)))>0)    {     e.flow+=f;edge[G[x][i]^1].flow-=f;flow+=f;a-=f;if(a==0) break;   }   } return flow; } int Maxflow(int s,int t) {  this->s=s;this->t=t;  int flow=0;  while(BFS())  {   memset(cur,0,sizeof(cur));  flow+=DFS(s,INF);  } return flow; }}sol;int main(){ int n,m; cin>>n>>m; for(int i=0;i<m;i++) {  int u,v,cap;  cin>>u>>v>>cap;  sol.addEdge(u,v,cap); } cout<<sol.Maxflow(1,n)<<endl; return 0;}

1:最大权闭合子集:http://www.cnblogs.com/TreeDream/p/5942354.html#_label0
可视作二分图 序偶(A R B) 变为闭合子集,后用网络流求解

#include<iostream>#include<cstring>#include<cstring>#include<queue> using namespace std;#define maxn 505#define INF 0x3f3f3f3fstruct Edge//边 { int from,to,cap,flow;};struct Dinic{ int n,m,s,t; vector<Edge>edge;//边  vector<int> G[maxn];//闭合子集  bool vis[maxn];//分层 标记  int d[maxn];//? int cur[maxn];//? void init()//输入前赋初值操作  {  for(int i=0;i<maxn;i++)  G[i].clear(); edge.clear();// queue清空用 clear memset(d,0,sizeof(d)); memset(vis,0,sizeof(vis)); memset(cur,0,sizeof(cur));  } void addEdge(int from,int to,int cap)//建边  {  edge.push_back((Edge){from,to,cap,0});//建正边  edge.push_back((Edge){to,from,0,0});//建逆边  m=edge.size();//?  G[from].push_back(m-2);//?  G[to].push_back(m-1); //? } bool BFS()//建分层网络  {   memset(vis,0,sizeof(vis));  queue<int>Q;  Q.push(s);  d[s]=0;  vis[s]=1;  while(!Q.empty())  {   int x=Q.front();   Q.pop();   for(int i=0;i<G[x].size();i++)   {    Edge &e=edge[G[x][i]]; if(!vis[e.to]&&e.cap>e.flow)//日常两个条件  {  vis[e.to]=1;  d[e.to]=d[x]+1;  Q.push(e.to);  }    }   }   return vis[t];//汇点在图里;  } long long DFS(int x,int a) {  if(x==t||a==0) return a;//增广到最后一点返回   long long flow=0,f;  for(int &i=cur[x];i<G[x].size();i++)   {   Edge&e=edge[G[x][i]];   if(d[x]+1==d[e.to]&&(f=DFS(e.to,min(a,e.cap-e.flow)))>0)//   {     e.flow+=f;  edge[G[x][i]^1].flow-=f;  flow+=f;  a-=f;  if(a==0) break;  }  }  return flow; } int Maxflow(int s,int t) {  this->s=s;this->t=t;  int flow=0;  while(BFS())  {   memset(cur,0,sizeof(cur));   flow+=DFS(s,INF);  }  return flow; }  //求最小割S,T void new_BFS(int s,int n) {  memset(vis,0,sizeof(vis));  d[s]=0;  vis[s]=1;  queue<int>Q;  Q.push(s);  while(!Q.empty())  {   int u=Q.front();   Q.pop();   for(int i=0;i<G[u].size();i++)   {    Edge&e= edge[G[u][i]]; if(!vis[e.to]&&e.cap>e.flow) {  vis[e.to]=1;  d[e.to]=d[u]+1;  Q.push(e.to);  }    }   }   int cnt=0;  for(int i=1;i<=n;i++)   if(vis[i])    cnt++;  cout<<cnt<<endl;  for(int i=1;i<=n;i++)   if(vis[i])    cout<<i<<" ";  puts(""); } }sol;int main(){ sol.init();//?? int n,m;//n活动,m人  cin>>n>>m; int s=0;//源点  int t=n+m+1;//汇点  int cap; for(int i=1;i<=m;i++) {  cin>>cap;//人消耗的活跃度   sol.addEdge(n+i,t,cap);//建边,负权边联接到汇点t  }  int sum=0; for(int i=1;i<=n;i++) {  int a,k;  sum+=a;//活动产生的总活跃度 sol.addEdge(s,i,a);// 建边,正权边连接到源点s for(int j=0;j<k;j++)//A到B间建立关系,赋值无穷  {  int v;  cin>>v;  sol.addEdge(i,v+n,INF);  }  } cout<<sum-sol.Maxflow(s,t)<<endl;//最大权闭合子图=正点和-最小割。 return 0; } 

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
原文链接:https://blog.csdn.net/weixin_43540515/article/details/89608809

宝塔服务器面板,一键全能部署及管理,送你3188元礼包,点我领取

扫描二维码推送至手机访问。

版权声明:文章来源于互联网公开页面遵守互联网分享协议,若涉及侵权请联系客服处理。

本文链接:https://www.idchg.com/info/277173/

发表评论

访客

看不清,换一张

◎欢迎参与讨论,请在这里发表您的看法和观点。