首页 > 代码库 > POJ 2677 Tour 双调旅行商 dp, double+费用流
POJ 2677 Tour 双调旅行商 dp, double+费用流
题目链接:点击打开链接
题意:给定二维平面上的n个点
从最左端点到最右端点(只能向右移动)
再返回到到最右端点(只能向左移动,且走过的点不能再走)
问最短路。
费用流:
为了达到遍历每个点的效果
把i点拆成 i && i+n
在i ->i+n 建一条费用为 -inf 的边,流量为1
这样跑最短路时必然会经过这条边,以此达到遍历的效果。
dp :点击打开链接
对于i点 :只能跟一个点相连 --
1、跟 i-1点相连
2、不跟i-1相连
用dp[i][j] 表示两个线头为 i 和 j 的状态(默认i>j)
已经计算出了dp[i-1]的所有状态
那么对于第一种情况对应的状态就是 dp[i][i-1]
dp[i][i-1] = min(dp[i-1][j]+dis[i][i-1]):就是从 线头为 i-1 和 j 的状态,把i和i-1的点相连
另外一种同理。
#include <stdio.h> #include <string.h> #include <iostream> #include <math.h> #include <queue> #include <set> #include <algorithm> #include <stdlib.h> using namespace std; #define ll int #define N 1005 #define inf 1152921504606846976 struct node{ double x, y; bool operator<(const node&a)const{ if(a.x==x)return a.y>y; return a.x>x; } }p[N]; double Dis(node a, node b){return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));} int n; double dis[N][N],dp[N][N]; int main(){ ll i, j, u, v; while(~scanf("%d",&n)){ for(i=1;i<=n;i++)scanf("%lf %lf",&p[i].x,&p[i].y); sort(p+1,p+n+1); for(i=1;i<=n;i++)for(j=1;j<=n;j++)dis[i][j] = Dis(p[i],p[j]), dp[i][j] = inf; dp[1][1] = 0; for(i=2;i<=n;i++) { for(j = 1;j < i; j++) { dp[i][j] = min(dp[i-1][j]+dis[i][i-1], dp[i][j]); dp[i][i-1] = min(dp[i-1][j]+dis[j][i], dp[i][i-1]); } } printf("%.2lf\n",dp[n][n-1]+dis[n][n-1]); } return 0; }
费用流:
#include <stdio.h> #include <string.h> #include <iostream> #include <math.h> #include <queue> #include <set> #include <algorithm> #include <stdlib.h> using namespace std; #define ll int #define N 1005 #define M 1234567 #define inf 1000000 #define eps (1e-6) //注意 点标必须是 [0 - 汇点] //双向边,注意RE struct Edge{ ll from, to, flow, cap, nex; double cost; }edge[M*2]; ll head[N], edgenum; void add(ll u,ll v,ll cap,double cost){//网络流要加反向弧 Edge E={u, v, 0, cap, head[u], cost}; edge[edgenum]=E; head[u]=edgenum++; Edge E2={v, u, 0, 0, head[v], -cost}; //这里的cap若是单向边要为0 edge[edgenum]=E2; head[v]=edgenum++; } double D[N]; ll P[N],A[N]; bool inq[N]; bool BellmanFord(ll s, ll t, ll &flow, double &cost){ for(ll i=0;i<=t;i++) D[i]= inf; memset(inq, 0, sizeof(inq)); D[s]=0; inq[s]=1; P[s]=0; A[s]=inf; queue<ll> Q; Q.push( s ); while( !Q.empty()){ ll u = Q.front(); Q.pop(); inq[u]=0; for(ll i=head[u]; i!=-1; i=edge[i].nex){ Edge &E = edge[i]; if(E.cap > E.flow && D[E.to] > D[u] +E.cost+eps){ D[E.to] = D[u] + E.cost ; P[E.to] = i; A[E.to] = min(A[u], E.cap - E.flow); if(!inq[E.to]) Q.push(E.to) , inq[E.to] = 1; } } } if(abs(D[t] - inf)<eps) return false; flow += A[t]; cost += D[t] * (double)A[t]; ll u = t; while(u != s){ edge[P[u]].flow += A[t]; edge[P[u]^1].flow -= A[t]; u = edge[P[u]].from; } return true; } double Mincost(ll s,ll t){//返回最小费用 ll flow = 0; double cost = 0; while(BellmanFord(s, t, flow, cost)); return cost; } void init(){memset(head,-1,sizeof head); edgenum = 0;} struct node{ double x, y; }p[N]; double dis(node a, node b){return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));} int n; int main(){ ll i, j, u, v; while(~scanf("%d",&n)){ init(); for(i=1;i<=n;i++)scanf("%lf %lf",&p[i].x,&p[i].y); for(i=1;i<=n;i++) { add(i,i+n,1,-inf); for(j = i+1;j<=n;j++) add(i+n,j,1,dis(p[i],p[j])); } add(1,1+n,1,0); add(n,n+n,1,0); printf("%.2lf\n",Mincost(1,n+n)+n*inf); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。