设为首页 加入收藏

TOP

POJ 2135 Farm Tour 最小费用最大流(一)
2012-11-10 11:52:00 】 浏览:874
Tags:POJ  2135  Farm  Tour  最小 费用 最大

    题意:FJ带朋友参观自己的农场,从自己的房子出发到barn(谷仓、畜棚或车库),再从barn返回自己的房子,要求去回不走同一条路。
   
    建图:取超级源点,并与房子连一条边,容量为2;取barn与超级汇点间的边的容量为2,中间的建图方法如代码。
   
    代码:
   
    [cpp]
   
    #include<iostream>
   
    #include<queue>
   
    #define maxe 400005
   
    #define maxn 1005
   
    #define INF 0x7fffffff
   
    using namespace std;
   
    struct Edge
   
    {
   
    int v,next;
   
    int p,f;
   
    Edge(int vv,int pp,int ff,int x):v(vv),p(pp),f(ff),next(x){}
   
    Edge(){}
   
    } e[maxe];
   
    int dist[maxn],vis[maxn],cur[maxn];
   
    int size,pre[maxn],head[maxn],mimf;
   
    /*
   
    最小费用最大流:
   
    用最短路算法在图上找到一条最小费用的增广路径
   
    因为流量可以回退,即有负值边,采用SPFA或者Bellman_Ford.
   
    在找到的最短路上面修改流量(跟最大流算法一致)
   
    每条路径的费用为  mimf*dist[T](该路径上的能通过的最大的流*每单位流量的费用)

   

首页 上一页 1 2 下一页 尾页 1/2/2
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇多重背包+二进制优化 下一篇一个简易画板的实现(Graphics..

最新文章

热门文章

Hot 文章

Python

C 语言

C++基础

大数据基础

linux编程基础

C/C++面试题目