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

OI之路,漫漫人生

只为梦想,没有理由

 
 
 

日志

 
 

POJ2135Farm Tour题解  

2014-03-19 23:32:17|  分类: POJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
                                                                    农场的旅程
                                                     BY   LGS
题目大意:给出一个无向有正权图,问从出发点到终点然后返回的每条边最多经过一次的最短路径(除了出发点和终点)。要从出发点到终点再返回。

题解:裸的费用流题目,作为我的第一次费用流模板。具体算法见下方推荐阅读。

总结:基础题。

代码:
#include<cstdio>
#include<cstring>
#define maxn 20000
#define maxm 12000
#define maxx 99999999
using namespace std;
int x,y,c,i,j,n,m,h,t,tot,k,ans;
int fa[maxn],queue[maxn],pre[maxn],dis[maxn];
bool vis[maxn];
struct node{int start,next,end,cost,f;
}g[maxm*5];
void add(int a,int b,int v)
 {g[tot].end=b;g[tot].start=a;g[tot].cost=v;
  g[tot].next=fa[a];fa[a]=tot;
  g[tot].f=1;tot++;
  
 
  g[tot].end=a;g[tot].start=b;g[tot].cost=-v;
  g[tot].next=fa[b];g[tot].f=0;fa[b]=tot;
  tot++;
 }
void spfa()
 {
 int i,w,h,t;
 memset(vis,false,sizeof(vis));
 for (i=1;i<=n;i++) dis[i]=maxx;memset(queue,0,sizeof(queue));
 for (i=1;i<=n;i++) pre[i]=-1;
 queue[1]=1;vis[1]=true;
 h=0;t=1;dis[1]=0;
 while (h<=t) {
             w=queue[++h];
             for (i=fa[w];i!=-1;i=g[i].next)
             if ((dis[g[i].end]>dis[w]+g[i].cost)&&(g[i].f>0))
                   {
                   dis[g[i].end]=dis[w]+g[i].cost;
                   pre[g[i].end]=i;
                   
                   if (!vis[g[i].end]){
                                      vis[g[i].end]=true; 
                                      queue[++t]=g[i].end; 
                                       } 
                   }
             vis[w]=false;
             }
 }
int main()
{
 scanf("%d%d",&n,&m);
 ans=0;  memset(fa,-1,sizeof(fa));
 for (i=1;i<=m;i++){
       scanf("%d%d%d",&x,&y,&c);
       add(x,y,c);add(y,x,c);            
                   }
for (k=1;k<=2;k++){
    spfa();ans+=dis[n];
         for (i=pre[n];i!=-1;i=pre[g[i].start])
        {g[i].f-=1;g[i^1].f+=1;}       
                  }
printf("%d\n",ans);
return 0;
}

  评论这张
 
阅读(525)| 评论(1)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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