poj 2135

本文主要是介绍poj 2135，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

       这道题可以用费用流来解决，在大神看来可能是一道水题，不过对于我这种菜鸟，还是想不到。

       看到这道题，开始想到用两次最短路算法，不过感觉有问题，比如说在某些特殊的情况下，最短路求出的路径可能使得题目无解，具体来说就是如果不走最短路，那么有两条路径，但每条路的权值都比最短路大，如果选择最短路的路径，则不存在另外一条从1到n的路径，即只有最短路径一条路径可走，比如说有一条对角线的矩形，起点和终点在没有对角线的那两个端点上，给予适当的权值就会出现那种情况。后来又想求一个包含房子和仓库的最小环，想在基于Floyd算法求最小环的算法上改改，不过很久没写了，不会了，而且复杂度略高，也放弃了。最后，参考了一下书（《挑战程序设计竞赛》人民邮电出版社 P238），才明白用费用流解决。

      题目给出的边容量都为1，加上一条容量为2，从超级源点指向1顶点的弧， 然后通过费用流选出两条权值和最小的路径。

代码（C++）：

#include <cstdlib>
#include <iostream>
#include <queue>#define MAX 1050
#define INF (1<<30)
using namespace std;//#define LOCALstruct Edge{int u;  int v;int cap;int w;int next;  
} edge[MAX*10*2*2];int head[MAX],c,dist[MAX],n,pre[MAX],ans;
bool inq[MAX];void add_edge(int u,int v,int cap,int w)
{edge[c].u=u; edge[c].v=v;edge[c].cap=cap;edge[c].w=w;edge[c].next=head[u];head[u]=c;c++;edge[c].u=v;edge[c].v=u;edge[c].cap=0;edge[c].w=-w;edge[c].next=head[v];head[v]=c;c++;
}void spfa(int s)
{int i,u,v;queue<int> qi;for(i=0;i<=n;i++){dist[i]=INF;inq[i]=false;pre[i]=i;}dist[s]=0;qi.push(s);inq[s]=true;while(!qi.empty()){u=qi.front();qi.pop();inq[u]=false;for(i=head[u];i!=-1;i=edge[i].next){v=edge[i].v;                               if(edge[i].cap>0&&dist[u]+edge[i].w<dist[v]) {dist[v]=dist[u]+edge[i].w;pre[v]=i;if(!inq[v]){qi.push(v);inq[v]=true;       }}                              }              }
}int add_flow(int s,int v,int f)
{int e,d;if(s==v) return f;e=pre[v];d=add_flow(s,edge[e].u,min(f,edge[e].cap));edge[e].cap-=d;edge[e^1].cap+=d;ans+=edge[e].w*d;return d;
}int min_cost_f(int s,int t)
{ans=0;while(1){spfa(s);if(dist[t]==INF) return ans;add_flow(s,t,INF);        }    
}int main(int argc, char *argv[])//源点：0     汇点：n 
{
#ifdef LOCALfreopen("in.txt","r",stdin);freopen("out.txt","w",stdout);
#endifint m,a,b,w,i;while(scanf("%d %d",&n,&m)!=EOF){c=0;memset(head,-1,sizeof(head));            for(i=0;i<m;i++){scanf("%d %d %d",&a,&b,&w);add_edge(a,b,1,w); add_edge(b,a,1,w);          }add_edge(0,1,2,0); printf("%d\n",min_cost_f(0,n));                  }system("PAUSE");return EXIT_SUCCESS;
}

Description

Input

Output

Sample Input

4 5
1 2 1
2 3 1
3 4 1
1 3 2
2 4 2

Sample Output

6

这篇关于poj 2135的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！