频道栏目
首页 > 考试 > 其他 > 正文

Island Transport (无向图Dinic算法+当前弧优化)

2018-06-08 02:46:03      个评论    来源:EnjoyingAC的博客  
收藏   我要投稿

Island Transport (无向图Dinic算法+当前弧优化)

读题

给定一个无向图,求从最左侧的点到最右侧的点的最大流。

解题

无向图的最大流与有向图的最大流的区别在于反向边的流量不是零而是与正向边相等。注意这点之后,再打一个Dinic算法模板。考虑到数据特别地大,需要进行当前弧优化。即在每一次找增广路前进行:

while(bfs())
 {
  for(int i=1;i<=N;i++)
cur[i]=head[i];
  ans+=dfs(S,INF);
 }

并且在dfs中,及将i=head[u]改成:

for(int &i=cur[u];i!=-1;i=e[i].next)

AC代码

//8923ms 15MB
#include 
#include 
#include 
#include 
#include
#include 
#include 
#include 
#define INF 0x3f3f3f3f
using namespace std;

int S,T;//源点和汇点
const int maxe=1e5+1000;
const int maxv=1e5+100;
struct edge
{
 int to,w,next;
}e[maxe<<1];
int N,M;
int head[maxv<<1],depth[maxv],cnt;
int cur[maxv<<1];//当前弧优化
void init()
{
 memset(head,-1,sizeof(head));
 cnt=-1;
}
void add_edge(int u,int v,int w)
{
 e[++cnt].to=v;
 e[cnt].w=w;
 e[cnt].next=head[u];
 head[u]=cnt;
}
void _add(int u,int v,int w)
{
 add_edge(u,v,w);
 add_edge(v,u,w);
}

bool bfs()
{
 queue q;
 while(!q.empty()) q.pop();
 memset(depth,0,sizeof(depth));
 depth[S]=1;
 q.push(S);

 while(!q.empty())
 {
  int u=q.front();q.pop();
  for(int i=head[u];i!=-1;i=e[i].next)
  {
if(!depth[e[i].to] && e[i].w>0)
{
 depth[e[i].to]=depth[u]+1;
 q.push(e[i].to);
}
  }
 }
 if(!depth[T]) return false;
 return true;
}
int dfs(int u,int flow)
{
 if(u==T || flow==0) return flow;
 int ret=0,tmp;
 for(int &i=cur[u];i!=-1;i=e[i].next)
 {
  if(depth[u]+1==depth[e[i].to] && e[i].w>0)
  {
int v=e[i].to;
if(depth[v]==depth[u]+1 && (tmp=dfs(v,min(flow,e[i].w)))>0)
{
 flow-=tmp;
 ret+=tmp;
 e[i].w-=tmp;
 e[i^1].w+=tmp;
 if(flow==0) break;
}
  }
 }
 return ret;
}
int Dinic()
{
 int ans=0;
 while(bfs())
 {
  for(int i=1;i<=N;i++)
cur[i]=head[i];
  ans+=dfs(S,INF);
 }
 return ans;
}

int main()
{
 int kase;
 scanf("%d",&kase);
 while(kase--)
 {
  init();
  scanf("%d%d",&N,&M);
  int minv=INF,maxv=-INF;
  for(int i=1;i<=N;i++)
  {
int x,y;
scanf("%d%d",&x,&y);
if(xmaxv) maxv=x,T=i;
  }
  for(int i=1;i<=M;i++)
  {
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
_add(u,v,w);//注意双向边,不要建流量为0的反边,只有建两条流量都为w的边
  }
  printf("%d\n",Dinic());
 }
 return 0;
}
上一篇:编程开发猜数字游戏问题解析
下一篇:循环有序数组最小值问题解析
相关文章
图文推荐

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站