解题报告之POJ3686TheWindy's

作者:网络    软件教程库   2020-05-21

解题报告 之 poj3686 the windy‘s


description

the windy‘s is a world famous toy factory that ownsmtop-class workshop to make toys. this year the manager receivesnorders for toys. the manager knows that every order will take different amount of hours in different workshops. more precisely, thei-th order will takezijhours if the toys are making in thej-th workshop. moreover, each order‘s work must be wholly completed in the same workshop. and a workshop can not switch to another order until it has finished theprevious one. the switch does not cost any time.

the manager wants to minimize the average of the finishing time of thenorders. can you help him

input

the first line of input is the number of test case. the first line of each test case contains two integers,nandm(1 ≤n,m≤ 50).
the nextnlines each containmintegers, describing the matrixzij(1 ≤zij≤ 100,000) there is a blank line before each test case.

output

for each test case output the answer on a single line. the result should be rounded to six decimal places.

sample input

3

3 4
100 100 100 1
99 99 99 1
98 98 98 1

3 4
1 100 100 100
99 1 99 99
98 98 1 98

3 4
1 100 100 100
1 99 99 99
98 1 98 98

sample output

2.000000
1.000000
1.333333


题目大意:有n个玩具要生产,有m个工厂,每个工厂同时只能加工一个玩具,给出每个工厂生产不同玩具所需的时间,问每个玩具生产平均需要花的时间最少为多少?


分析:这个题比较抽象,不是很好想明白。首先很简单可以得到的结论是:如果只有一个工厂,那么它一定是先生产时间少的玩具,再生产时间多的玩具(想想为啥?)。那么最终这个工厂花费的时间就是 t = z1#43;(z1#43;z2)#43;(z1#43;z2#43;z3)#43;……#43;(z1#43;z2#43;z3……#43;zn) 。 化简得到:

t = n*z1#43;(n-1)*z2#43;(n-2)*z3#43;……#43;zn。 **

注意这个公式要从抽象的层面去看待,不要试图寻找其中的含义不然会很绕。


然后我们的大问题就转化为,将n种玩具分配给m家工厂,每家工厂都按照上述的最佳策略去生产分配到的玩具。即我们现在需要考虑的是,如何分配这n种玩具?首先很明显枚举肯定超,就不说了。那么我们怎么想呢,这里借助了最小费用流的想法。先考虑简单的情形:如果问题是每个厂家仅分配一个玩具,那么直接上最小费用流跑即可。这里变成了多个厂家,我们根据**公式,假设一个厂家分配到了一些玩具,假设为k个玩具好了,那么它就按照上面的公式运算即可。那某个厂家到底分配到了几个玩具,又是哪几个呢?这里我们交给最小费用流去试验,而没有一种确定的方法。


具体操作是,超级源点连接没一个玩具节点,负载为1,费用为0。然后将每个厂家分成n个节点,厂家j的第k个节点表示**公式中的系数k(k=1,2,3……n)应的是哪个玩具 i,当然费用对应的增长k*cost[j][i]。当然对于每一个厂家,不一定1~n都有玩具,这交给最小费用流去解决。然后每个厂家的所有节点都连接到超级汇点。最后跑最小费用流min_cost_flow(n)即可自动规划出一条最优方案。


q:如果某玩具选择了厂家k较大的一条路但该厂家k小的路却没用怎么办?

a:不会出现这种情况,因为是最小费用流,当然会优选k小的路。


q:如果多个玩具同时选了厂家j的系数k节点不是就重复了么?

a:不会,建图的时候厂家j的系数k节点连到des负载为1,所以不会重复。


上代码:

#includeiostream
#includecstdio
#includealgorithm
#includecstring
#includequeue
#includedeque
using namespace std;

const int maxn = 3010;
const int maxm = 1100000;
const int inf = 0x3f3f3f3f;

struct edge
{
	int from, to, cap, next, cost;
};

edge edge[maxm];
int prevv[maxn];
int preve[maxn];
int dist[maxn];
int head[maxn];
int h[maxn];   //标号数组
int cost[maxn][maxn];
int src, des, cnt;

void addedge( int from, int to, int cap, int cost )
{
	edge[cnt].from = from;
	edge[cnt].to = to;
	edge[cnt].cap = cap;
	edge[cnt].cost = cost;
	edge[cnt].next = head[from];
	head[from] = cnt++;

	swap( from, to );

	edge[cnt].from = from;
	edge[cnt].to = to;
	edge[cnt].cap = 0;
	edge[cnt].cost = -cost;
	edge[cnt].next = head[from];
	head[from] = cnt++;
}

int spfa( )
{
	dequeint dq;
	bool inqueue[maxn];
	memset( dist, inf, sizeof dist );
	memset( inqueue, 0, sizeof inqueue );
	dq.push_back( src );
	inqueue[src] = 1;
	dist[src] = 0;
	while(!dq.empty( ))
	{
		int u = dq.front( );
		dq.pop_front( );

		inqueue[u] = 0;

		for(int i = head[u]; i != -1; i = edge[i].next)
		{
			int v = edge[i].to;
			if(edge[i].cap  0  dist[u] + edge[i].cost + h[u] - h[v] dist[v])
			{
				dist[v] = dist[u] + edge[i].cost + h[u] - h[v];
				prevv[v] = u;
				preve[v] = i;
				if(!inqueue[v])
				{
					if(!dq.empty( )  dist[v] = dist[dq.front( )])
					{
						dq.push_front( v );
					}
					else
						dq.push_back( v );
				}
			}

		}

	}
	return 0;
}

int min_cost_flow( int f )
{
	memset( h, 0, sizeof h );
	int cost = 0;
	while(f  0)
	{
		spfa( );
		if(dist[des] == inf)
		{
			return -1;
		}
		for(int u = 1; u  maxn; u++)
			h[u] += dist[u];

		int d = f;
		for(int i = des; i != src; i = prevv[i])
		{
			d = min( d, edge[preve[i]].cap );
		}

		f -= d;
		cost += d*h[des];
		for(int i = des; i != src; i = prevv[i])
		{
			edge[preve[i]].cap -= d;
			edge[preve[i] ^ 1].cap += d;
		}
	}
	return cost;
}

int main( )
{
	int n, m;
	int kase;
	cin  kase;
	src = 0;
	des = 3005;
	while(kase--)
	{
		cin  n  m;
		memset( head, -1, sizeof head );
		cnt = 0;
		for(int i = 1; i = n; i++)
		{
			for(int j = 1; j = m; j++)
			{
				cin  cost[i][j];
			}
		}

		for(int i = 1; i = n; i++)
		{
			addedge( src, i, 1, 0 );
		}

		for(int j = 1; j = m; j++)
		{
			for(int k = 1; k = n; k++)
			{
				addedge( j * 50 + k, des, 1, 0 );
				for(int i = 1; i = n; i++)
				{
					addedge( i, j * 50 + k, 1, k*cost[i][j] );
				}
			}
		}


		printf( %.6lf\n, min_cost_flow( n ) / (double)n );
	}
	return 0;
}


~ 代码狗祝你劳动节快乐 ~

技术分享

解题报告 之 poj3686 the windy#39;s

原文地址:http://blog.csdn.net/maxichu/article/details/45421255

该篇内容就是由软件教程库(原文链接:https://www.itjcku.com/9999/1091551.html)小编为各位整理

阅读全部内容


Tags:解题报告讲演呈文

返回首页



推荐内容

【ThinkingInJava】18、关于java中的闭包与回调

/** * 书本:《thinking in java》 * 功能:关于java中的闭包与回调,这里回调区别于c++,c+ ...

TreasureHunting (hdu3468二分匹配+bfs最短路径)

treasure hunting time limit: 4000/2000 ms (java/others)mem ...

【ThinkingInJava】19、控制框架的实现

/** * 书本:《thinking in java》 * 功能:控制框架的实现 * 文件:event.java * 时 ...

【ThinkingInJava】20、控制框架的使用(初始化系统使用)

/** * 书本:《thinking in java》 * 功能:控制框架的实现,1、控制框架的完整实现是由单个的类创建 ...

最小汉密尔顿回路问题状态压缩dp

给定n个顶点做成的图,要求从顶点0出发经过所有点一次然后回到0点的一条权#20540;之和最小的一条路的权#20540; ...

POJ1966.CableTVNetwork——无向图的点连通度

http://poj.org/problemid=1966 题目描述: 有线电视网络中,中继器的连接是双向的。如果网 ...

Oracle备忘录1

数据库管理员:安装升级oracle数据库建库,表空间,表,视图,索引。。。制定并实施备份和修复计划数据库权限管理,调优, ...

FileStream文件流

使用文件流拷贝一个较大的多媒体文件: public static void copyfile(string soucr ...

C语言BFS(5)___TT与魔法师(swustoj2464)

description tt生活在一个充满魔法的国度,为了便于管理,国王请魔法师在一些重要的城市之间造出 ...

进程类Process与多线程Thread

进程类(process)的基本操作: //通过进程类查询系统所有进程 process[] pr ...

Xml解析方式之Pull解析器的使用

xml有多种解析的方式,这篇文章只介绍用pull解析器来解析xml文件,接下来我会说明使用pull解析器来读取xml文件 ...

enum,EnumMap,EnumSet

enum基本使用 : package com.enumtest; enum shrubbery { gr ...

Hibernate乱码问题解决

乱码问题其实归根接地就是两端的字符集不统一。 解决思路也有两种: 1. 修改两端字符集统一。 2. 通过代码进行转 ...

eclipse集成struts2.3.20

需要强调的是,这里介绍的是在eclipse工具下集成struts2.3.20而不是myeclipse添加对struts2 ...

ubi文件系统制作,还是"-c"选项的问题

以下是分析记录: --------------------------------------------------- ...

如何把事情做到最好读书笔记1

开篇语: 每个人生来都具备足够的潜力,每个人都能做到别人#30524;中难以企及的事情。请永远保持初学之心,勇敢面对 ...

如何把事情做到最好读书笔记2

第二章 认清自己:你属于哪种类型的人 你必须足够了解你自己,下面有三种类型的人、 (1)浅尝辄止者 浅尝辄止者对一切 ...

如何把事情做到最好读书笔记3

第三章 一份耕耘才能一份收获 当你决定踏上精益求精之路时,你会突然发现周围的一切都与你所追求的#26684;#2668 ...

如何把事情做到最好读书笔记4

第四章 热爱平台期 从小,我们接受的教育就是好好学习,这样才能上好的大学,上好的大学才能找到好工作,有好工作才能有钱买 ...

习题10-21二项式系数UVa1649

1.题目描述:点击打开链接 2.解题思路:本题利用枚举#43;二分解决。问题的关键是选对枚举对象,因为要找c(n,k)= ...

mysql小技巧

selectnow(),user(),version(),database(); #最后输入\c是放弃的意思 des ...

Java学习笔记——面试常客:写出一个死锁的例子

现在的面试挺蛋疼,为了考察大家的语言掌握水平,类#20284;这样的题特别多,不过在某个角度来说确实能看出一个人对某个知 ...

UVA-10396VampireNumbers暴力+打表

题目大意:给出n,要求你输出所有符合规则的n位数 规则如下,这个n位数由两个n/2位数相乘得到,并且满足 1.这n位 ...

CF148D.Bagofmice[概率dp]

题目链接:http://codeforces.com/problemset/problem/148/d 题目大意:一袋子 ...

HDU-1846-BraveGame(巴什博弈)

题目传送:brave game 介绍: 巴什博奕(bash game): 首先我们来玩一个比较古老的报数游戏。a ...

HDU-2149-PublicSale(巴什博弈)

题目传送:public sale 思路:巴什博弈 ac代码: #include lt;cstdiogt; # ...

enum实现售卖机

首先 推荐一下google的代码风格 :https://google-styleguide.googlecode ...

批量添加用户

a、创建用户文件,因为添加的用户比较多,因此编写脚本创建一个用户文件user.txt #!/bin/ba ...

解决侧滑中ViewPager和SlidingMenu的滑动冲突

当我们在使用开源框架slidingmenu时,如果要是使用到viewpager,就会出现滑动冲突。 解决方案: }/** ...

shell打乱文件行

思路,产生一个随机数组,然后按按照数组的元素将文件中行的重新输出 1、随机数组的生成 看书的时候感觉很是简单。第 ...


本网站部分内容来自互联网,版权归原作者所有,文章内容仅代表原作者个人观点。如有侵权请联系我们删除 电子邮件 itjcku@foxmail.com