| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 3408 | Accepted: 1513 |
Description
Input
Output
Sample Input
3 1 1 2 3 3 1 4 1 1 2 3 3 1 4 2
Sample Output
一旅行商从左向右走到最右边，然后再返回原来出发点的最短路径。
两种做法，第一种dp，dp[i][j]表示以i，j结尾的两条不相交的路径假设i一定大于j，i有两种选择，与i-1相连，不与i-1相连，然后dp
代码：
#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 100000000
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)){//dp[i][j]表示以i，j为结尾的两条不相交的路径
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]);//i不与i-1相连，
dp[i][i-1] = min(dp[i-1][j]+dis[j][i], dp[i][i-1]);//i与i-1相连。
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++)cout<<dp[i][j]<<" ";
cout<<endl;
}
printf("%.2lf\n",dp[n][n-1]+dis[n][n-1]);
}
return 0;
}
代表可以增广两次。
代码：
/* ***********************************************
Author :_rabbit
Created Time :2014/5/17 9:42:51
File Name :6.cpp
************************************************ */
#pragma comment(linker, "/STACK:102400000,102400000")
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <string>
#include <time.h>
#include <math.h>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
#define INF 1001000
#define eps 1e-8
#define pi acos(-1.0)
typedef long long ll;
const int maxn=4010;
const int maxm=200000;
struct Edge{
int next,to,cap;
double cost;
Edge(int _next=0,int _to=0,int _cap=0,double _cost=0){
next=_next;to=_to;cap=_cap;cost=_cost;
}
}edge[maxm];
int head[maxn],vis[maxn],pre[maxn],n,tol;
double dis[maxn];
void addedge(int u,int v,int cap,double cost){
edge[tol]=Edge(head[u],v,cap,cost);head[u]=tol++;
edge[tol]=Edge(head[v],u,0,-cost);head[v]=tol++;
}
bool spfa(int s,int t){
queue<int> q;
for(int i=0;i<=n;i++)
dis[i]=INF,vis[i]=0,pre[i]=-1;
dis[s]=0;vis[s]=1;q.push(s);
while(!q.empty()){
int u=q.front();q.pop();vis[u]=0;
// cout<<"u="<<u<<" "<<dis[u]<<endl;
for(int i=head[u];i!=-1;i=edge[i].next){
int v=edge[i].to;
if(edge[i].cap>0&&dis[v]>dis[u]+edge[i].cost){
dis[v]=dis[u]+edge[i].cost;
pre[v]=i;
if(!vis[v])vis[v]=1,q.push(v);
}
}
}
if(pre[t]==-1)return 0;
return 1;
}
void fun(int s,int t,int &flow,double &cost){
flow=0;cost=0;
while(spfa(s,t)){
int MIN=INF;
for(int i=pre[t];i!=-1;i=pre[edge[i^1].to])
if(MIN>edge[i].cap)MIN=edge[i].cap;
for(int i=pre[t];i!=-1;i=pre[edge[i^1].to])
edge[i].cap-=MIN,edge[i^1].cap+=MIN,cost+=edge[i].cost*MIN;
flow+=MIN;
}
}
struct Point{
double x,y;
}pp[10000];
double dist(Point a,Point b){
double ss=a.x-b.x;
double tt=a.y-b.y;
return sqrt(ss*ss+tt*tt);
}
int main(){
int m;
// freopen("data.out","w",stdout);
while(cin>>m){
memset(head,-1,sizeof(head));tol=0;
for(int i=1;i<=m;i++)cin>>pp[i].x>>pp[i].y;
for(int i=1;i<=m;i++){
for(int j=i+1;j<=m;j++){
double dd=dist(pp[i],pp[j]);
addedge(i+m,j,1,dd);
}
addedge(i,i+m,1,-INF);
}
addedge(1,m+1,1,0);
addedge(m,2*m,1,0);
n=2*m;
int flow;double cost;
fun(1,2*m,flow,cost);
printf("%.2lf\n",cost+m*INF);
}
return 0;
}POJ 2677 旅行商问题 双调dp或者费用流,布布扣,bubuko.com
原文：http://blog.csdn.net/xianxingwuguan1/article/details/26089461