POJ 3686 最小费用最大流(拆点建图)_poj3686-程序员宅基地

思路:这题还挺难的。刚开始看错题目意思了,然后建图错了得不出答案,然后看了下别人的题解,原来每个矩阵的点还在拆成n个点才得。

然后昨晚看了1个小时多小时没理解,今早过来再看,然后用别人的代码运行了一下我自己想出的样例,然后才慢慢理解。

解题分析:《参考博客:http://blog.csdn.net/weiguang_123/article/details/7881799》

 假设某个机器处理了k个玩具,那么对于这些玩具,有两种时间,一种是真正处理的时间,一种是等待的时间,等待的时间就是之前所有处理的玩具的时间,

假设这k个玩具真正用在加工的时间分为a1,a2,a3...ak, 那么每个玩具实际的时间是加工的时间+等待时间,分别为a1, a1+a2, a1+a2+a3.......a1+a2+...ak。求和之后变为 a1 *k + a2 * (k - 1) + a3 * (k - 2).... + ak

       这时就发现,每个玩具之间的实际时间可以分开来算 然后求和了。

       因为对每个机器,最多可以处理n个玩具,所以可以拆成n个点,1~n分别代表某个玩具在这个机器上倒数第几个被加工的, 所以我们对于每个玩具i,机器j中拆的每个点k,连接一条z[i][j]*k权值的边。

      建图:建立源汇点,源点和每个订单流量为1,费用为0;订单和每台机器拆成的点k建立流量为1,费用为Mij*k;

k与汇点建立流量为1,费用为0,求最小费用最大流即可。神吧这建图模型。


我自己想的样例是:

3  4

100 100 100 1
99 99 99 2
98 98 98 3

按口算应该是:1+(1+2)+(1+2+3)=10,按上面解题分析变成:1*3+2*2+3=10,所以1,2,3这个点被分解成了三个点了,1分解成:1,1*2,1*3;2分解成:2,2*2,2*3;3分解成:3,3*2,3*3。所以可以看出这里取的最佳路径为:1的点取1*3,2的点取2*2,3的点取3,意思即:在第4个机器上3先加工,然后第二个加工的是2,第三个加工的是1,所以答案为10与口算的一样,这样就可以建图用最小费用最大流求了。

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<queue>
#include<set>
#include<cmath>
#include<bitset>
#define mem(a,b) memset(a,b,sizeof(a))
#define lson i<<1,l,mid
#define rson i<<1|1,mid+1,r
#define llson j<<1,l,mid
#define rrson j<<1|1,mid+1,r
#define INF 0x7fffffff
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
#define maxn 300005
struct
{
    int v,w,c,next,re;
    //re记录逆边的下标,c是费用,w是流量
} e[maxn];
int n,cnt;
int head[maxn],que[maxn*8],pre[maxn],dis[maxn];
bool vis[maxn];
void add(int u, int v, int w, int c)
{
    e[cnt].v=v,e[cnt].w=w,e[cnt].c=c;
    e[cnt].next=head[u];
    e[cnt].re=cnt+1,head[u]=cnt++;
    e[cnt].v=u,e[cnt].w=0,e[cnt].c=-c;
    e[cnt].next=head[v];
    e[cnt].re=cnt-1,head[v]=cnt++;
}
bool spfa()
{
    int i, l = 0, r = 1;
    for(i = 0; i <= n; i ++)
        dis[i] = INF,vis[i] = false;
    dis[0]=0,que[0]=0,vis[0]=true;
    while(l<r)
    {
        int u=que[l++];
        for(i=head[u];i!=-1;i=e[i].next)
        {
            int v = e[i].v;
            if(e[i].w&&dis[v]>dis[u]+e[i].c)
            {
                dis[v] = dis[u] + e[i].c;
                pre[v] = i;
                if(!vis[v])
                {
                    vis[v] = true;
                    que[r++] = v;
                }
            }
        }
        vis[u] = false;
    }
    return dis[n]!=INF;
}
int change()
{
    int i,p,sum=INF,ans=0;
    for(i=n;i!=0;i=e[e[p].re].v)
    {//e[e[p].re].v为前向结点,不理解看add和spfa
        p=pre[i];//p为前向结点编号
        sum=min(sum,e[p].w);
    }
    for(i=n;i!=0;i=e[e[p].re].v)
    {
        p=pre[i];
        e[p].w-=sum;
        e[e[p].re].w+=sum;
        ans+=sum*e[p].c;//c记录的为单位流量费用,必须得乘以流量。
    }
    return ans;
}
int EK()
{
    int sum=0;
    while(spfa()) sum+=change();
    return sum;
}
void init()
{
    mem(head,-1),mem(pre,0),cnt=0;
}
int a[51][51];
int main()
{
    //freopen("1.txt","r",stdin);
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int N,M,i,j,k;
        init();
        scanf("%d%d",&N,&M);
        for(i=1;i<=N;i++)
            for(j=1;j<=M;j++)
                scanf("%d",&a[i][j]);
        for(i=1;i<=N;i++)
            add(0,i,1,0);
        for(i=1;i<=N;i++)
            for(j=1;j<=M;j++)
                for(k=1;k<=N;k++)
                    add(i,N+(j-1)*N+k,1,a[i][j]*k);
        for(j=1;j<=M;j++)
            for(k=1;k<=N;k++)
                add(N+(j-1)*N+k,N+N*M+1,1,0);
        n=N+N*M+1;
        printf("%.6f\n",EK()*1.0/N);
    }
    return 0;
}


版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/u011466175/article/details/38846053

智能推荐

Vue图片加载错误、图片加载失败的处理_swipe-vue中 加载图片失败-程序员宅基地

文章浏览阅读1.3k次。Vue图片加载错误、图片加载失败的处理注意:onerror前面要用冒号 :注意看logo定义的格式,符号不要写错了<img :src="pic?pic:'../../assets/placeholder.png'" :onerror="errorImage" alt=""> <script>export default { data() { return { errorImage: 'this.src="' _swipe-vue中 加载图片失败

fprintf用法解析-程序员宅基地

文章浏览阅读1w次,点赞6次,收藏26次。int fprintf ( FILE * stream, const char * format, ... );描述:写格式化的数据流将格式指向的C字符串写入流中。 如果格式包含格式说明符(以%开头的子序列),则格式化后的其他参数将被格式化并插入结果字符串中,替换其各自的说明符。在格式参数之后,函数至少需要格式指定的附加参数。参数:stream指向标识输出流的FIL_fprintf

Hibernate4不自动建表_hibernate 4 自动创建 表-程序员宅基地

文章浏览阅读940次。 hibernate.dialect=org.hibernate.dialect.MySQLDialect hibernate.hbm2ddl.auto=create hibernate.show_sql=true h_hibernate 4 自动创建 表

MAC下检查是否安装command line tools 工具_怎么查看mac有没有已安装command-line-tool-程序员宅基地

文章浏览阅读1.6w次。怎样判断「Command Line Tools」是否已经安装了呢?由 Sean.Lv 发布于 2013年10月26日 无人欣赏。升级到OS X Mavericks和Xcode5之后迷茫了,不知道「Command Line Tools」装了没?是否需要单独安装?猜你喜欢:怎样判断「Command Line Tools」是否已经安装了呢?_怎么查看mac有没有已安装command-line-tool

vue-baidu-map路书实现轨迹回放_bml-lushu-程序员宅基地

文章浏览阅读4.1k次,点赞2次,收藏7次。通过vue-baidu-map中路书来实现的,bml-lushu是用来还原行进轨迹的组件。_bml-lushu

SeetaFace2 测试_seetanet-程序员宅基地

文章浏览阅读4.5k次。核心网络 SeetaNetc++版,开源,是动态库,应该无源码有模型侧脸时关键点完全不对了,同时检测人脸有误检i7 1070 gpu 18ms,关键点 几乎0mscpu几乎一样,最快的还是ncnn的mtcnn,效果还更好。路径:SeetaFace2用cmake gui生成就可以。https://github.com/jacke121/SeetaFace2..._seetanet

随便推点

Unity3D_新版粒子系统_unity3.5之后推出粒子系统新版本的特点-程序员宅基地

文章浏览阅读818次。什么是粒子系统粒子系统表示三维计算机图形学中模拟一些特定的模糊现象的技术,而这些现象用其它传统的渲染技术难以实现的真实感的 game physics。经常使用粒子系统模拟的现象有火、爆炸、烟、水流、火花、落叶、云、雾、雪、尘、流星尾迹或者象发光轨迹这样的抽象视觉效果等等。新版粒子系统介绍Shuriken粒子系统是继Unity3.5版本之后推出的新版粒子系统,它采用了模块化管理,个性化的粒子模块配合..._unity3.5之后推出粒子系统新版本的特点

人工智能发展史_人工智能发展史 ppt-程序员宅基地

文章浏览阅读9.1k次,点赞2次,收藏7次。转自 微信公众号 纯洁的微笑人工智能的诞生:1943 - 1956在20世纪40年代和50年代,来自不同领域(数学,心理学,工程学,经济学和政治学)的一批科学家开始探讨制造人工大脑的可能性。1956年,人工智能被确立为一门学科。1956年的夏天,香农和一群年轻的学者在达特茅斯学院召开了一次头脑风暴式研讨会。会议的组织者是马文·闵斯基,约翰·麦卡锡和另两位资深科学家C_人工智能发展史 ppt

Django models存储json格式的数据_django数据库存json-程序员宅基地

文章浏览阅读4.9k次,点赞3次,收藏9次。JSONField官网介绍用于存储JSON格式数据的字段。在Python中,数据以其Python本机格式表示:字典,列表,字符串,数字,布尔值和None。一个可选的JSON格式类序列化的数据类型不是由标准JSON序列(支持的datetime,uuid等)。例如,您可以使用 DjangoJSONEncoder该类或任何其他json.JSONEncoder子类。JSONField使用..._django数据库存json

AXIS 访问webservice-程序员宅基地

文章浏览阅读385次。第一:先导入axis 的jar 包importorg.apache.axis.client.Call;importorg.apache.axis.client.Service;importorg.apache.axis.encoding.XMLType;第二:实际代码String url ="http://ip:1205/ws/OA.asm...

将我的ASP.NET网站从.NET 2.2 Core Preview 2升级到.NET 2.2 Core Preview 3-程序员宅基地

文章浏览阅读113次。I've recently returned from a month in South Africa and I was looking to unwind while the jetlagged kids sleep. I noticed that .NET Core 2.2 Preview 3 came out while I wasn't paying attention. My podc..._microsoft.aspnetcore.razor.design 从2.2.0降级到2.2.0-preview3-35497

联想危险!74 岁的创始人柳传志站了出来-程序员宅基地

文章浏览阅读5.1k次。&#13; &#13;&#13; &#13;&#13; &#13; &#13; 点击上方“CSDN”,选择“置顶公众号”关键时刻,第一时间送达中兴危机之时,76 岁的创始人侯为贵携..._联想出事博客