注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

OI之路,漫漫人生

只为梦想,没有理由

 
 
 

日志

 
 

DINIC  

2014-12-11 13:11:32|  分类: 算法杂类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
#include<cstdio>
#include<cstring>
#include<algorithm>
#define inf 2100000000
#define mm 250000
#define nn 510
#define CH getchar()
using namespace std;
struct nod{int end,next,c;
}g[mm*2];
 
int tot,i,n,z,ans,Dis,m;
int dis[nn],fa[nn],x[mm],y[mm],t[mm],c[mm],f[nn][nn],q[nn*4];
void folyed()
 {int k,i,j;
  for (i=1;i<=n;i++)f[i][i]=0;
  for (k=1;k<=n;k++)
  for (i=1;i<=n;i++)
   for (j=1;j<=n;j++)
   f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
 }
void add(int a,int b,int c)
 {g[tot]=(nod){b,fa[a],c};fa[a]=tot++;
  g[tot]=(nod){a,fa[b],0};fa[b]=tot++;
 }
bool bfs()
 {int t,w,i,u,x;
  memset(dis,-1,sizeof(dis));
  dis[q[1]=1]=0;
  for (t=0,w=1;t<w;){
  x=q[++t];if (x==n)return 1;
  for (i=fa[x];i!=-1;i=g[i].next)
  {u=g[i].end;
   if (dis[u]==-1&&g[i].c)
   {dis[u]=dis[x]+1;q[++w]=u;}
  }}
 return 0;
 }
int dfs(int w,int tem)
 {int c,i,u,ok=0;
  if (w==n)return tem;
  for (i=fa[w];i!=-1;i=g[i].next){
  u=g[i].end;
  if (dis[u]==dis[w]+1&&g[i].c){
  c=dfs(u,min(tem-ok,g[i].c));
  g[i].c-=c;g[i^1].c+=c;
  ok+=c;
  if (ok==tem)return tem;
  }
  }
  if (!ok)dis[w]=-1;
  return ok;
 }
int In()
 {char c;int tem=0;
  while (c=CH,c>'9'||c<'0');
  while (tem=tem*10+c-'0',c=CH,c>='0'&&c<='9');
  return tem;
 }
int main()
{
 n=In();m=In();
 memset(f,60,sizeof(f));
 for (i=1;i<=m;i++)
 {x[i]=In();y[i]=In();t[i]=In();c[i]=In();
  f[x[i]][y[i]]=f[y[i]][x[i]]=min(f[x[i]][y[i]],t[i]);}
 folyed();
 Dis=f[1][n];
 memset(fa,-1,sizeof(fa));
 for (i=1;i<=m;i++){
 z=f[1][x[i]]+f[y[i]][n]+t[i];
 if (z==Dis)add(x[i],y[i],c[i]); 
 z=f[1][y[i]]+f[x[i]][n]+t[i];
 if (z==Dis)add(y[i],x[i],c[i]);     
                   }
 while (bfs())ans+=dfs(1,inf);
 printf("%d\n%d\n",Dis,ans);
 return 0;
}

  评论这张
 
阅读(114)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018