设为首页 加入收藏

TOP

POJ 2135 Farm Tour && HDU 2686Matrix && HDU 3376Matrix Again 费用流求来回最短路
2015-07-20 18:04:05 来源: 作者: 【大 中 小】 浏览:2次
Tags：POJ 2135 Farm Tour & HDU 2686Matrix 3376Matrix Again 费用 来回 短路

累了就要写题解，最近总是被虐到没脾气。

来回最短路问题貌似也可以用DP来搞，不过拿费用流还是很方便的。

可以转化成求满流为2 的最小花费。一般做法为拆点，对于 i 拆为2*i 和 2*i+1，然后连一条流量为1（花费根据题意来定） 的边来控制每个点只能通过一次。

额外添加source和sink来控制满流为2。

代码都雷同，以HDU3376为例。

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
           #pragma comment(linker, "/STACK:1024000000"); #define EPS (1e-8) #define LL long long #define ULL unsigned long long #define _LL __int64 #define INF 0x3f3f3f3f #define Mod 6000007 using namespace std; const int EDGE = 6000000,POINT = 730000; struct E { int Max,cost,v,next; }edge[EDGE]; int head[POINT]; int Top; void Link(int u,int v,int w,int cost) { edge[Top].v = v; edge[Top].Max = w; edge[Top].cost = cost; edge[Top].next = head[u]; head[u] = Top++; } int Map[610][610]; int dis[POINT],cur[POINT],flow[POINT]; bool mark[POINT]; void Updata(int site,int flow,int &cost) { for(;cur[site] != -1; site = edge[cur[site]^1].v) { edge[cur[site]].Max -= flow; edge[cur[site]^1].Max += flow; cost += edge[cur[site]].cost * flow; } } queue
           
             q; int spfa(int S,int T,int &cost) { memset(mark,false,sizeof(mark)); memset(dis,INF,sizeof(dis)); cur[S] = -1,dis[S] = 0,flow[S] = INF; q.push(S); int f,t; while(q.empty() == false) { f = q.front(); q.pop(); mark[f] = false; for(int p = head[f];p != -1; p = edge[p].next) { t = edge[p].v; if(edge[p].Max && dis[t] > dis[f] + edge[p].cost) { dis[t] = dis[f] + edge[p].cost; cur[t] = p; flow[t] = min(flow[f],edge[p].Max); if(mark[t] == false) { mark[t] = true; q.push(t); } } } } if(dis[T] == INF) return 0; Updata(T,flow[T],cost); return flow[T]; } int Cal_Max_Flow_Min_Cost(int S,int T,int n) { int temp,flow = 0,cost = 0; do { temp = spfa(S,T,cost); flow += temp; }while(temp); return cost; } inline int Cal(int x,int y,int n) { return ((x-1)*n+y)*2-1; } int main() { int n; int i,j; while(scanf("%d",&n) != EOF) { memset(head,-1,sizeof(head)); Top = 0; for(i = 1;i <= n; ++i) { for(j = 1;j <= n; ++j) { scanf("%d",&Map[i][j]); if(i == j && (i == 1 || i == n)) Link(Cal(i,j,n),Cal(i,j,n)+1,2,-Map[i][j]); else Link(Cal(i,j,n),Cal(i,j,n)+1,1,-Map[i][j]); Link(Cal(i,j,n)+1,Cal(i,j,n),0,Map[i][j]); } } for(i = 1;i <= n; ++i) { for(j = 1;j <= n; ++j) { if(j < n) { Link(Cal(i,j,n)+1,Cal(i,j+1,n),1,0); Link(Cal(i,j+1,n),Cal(i,j,n)+1,0,0); } if(i < n) { Link(Cal(i,j,n)+1,Cal(i+1,j,n),1,0); Link(Cal(i+1,j,n),Cal(i,j,n)+1,0,0); } } } printf("%d\n",-Cal_Max_Flow_Min_Cost(1,n*n*2,n*n*2) - Map[1][1] - Map[n][n]); } return 0; }

【大 中 小】【打印】 【繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部】
分享到: 
上一篇：uva 548(二叉树) 下一篇：HDU 3047 Zjnu Stadium 带权并查集

评论

帐　　号: 密码: (新用户注册)
验 证 码:
表　　情:
内　　容: