问题背景
面对艰巨复杂的技术挑战，百度所崇尚的系统设计哲学是“简单可依赖”，而百度的工程师们正在互联网世界中实践着这种理念。这里正好有一个挑战，让作为百度之星的你小试牛刀：
在处理数以百亿计的网络信息的过程中，有一个很常见的问题：
怎么样将一个集群上的信息以最低的成本传输到另外一个集群上？
数据源集群A有n台服务器，编号为 1, 2, ..., n，i号服务器上待传输的数据量为Ai ，单位是GB。
目的地集群B有m台服务器，编号为 1, 2, ..., m，j号服务器上的空闲容量为 Bj，单位为 GB。
A集群的i号服务器上的每GB数据对于B的集群的j号服务器收益为Vi,j，从 A 集群的 i 号服务器向 B 集群的 j 号服务器传输 1GB数据的开销为Ci,j。
你的任务是在保证A中的所有数据传输完毕的前提下，性价比V/C尽量高。其中V为所有数据在B集群上的价值之和，C为总开销。换句话说，若A集群的i号服务器向B集群的j号服务器发送了Ti,j个GB的数据（Ti,j不一定是整数），则性价比定义为：
输入格式
第1行两个整数n, m(1<=n,m<=50)，即集群A和B各自的服务器台数。
第2行包含n个不超过100的正整数A1,A2,…,An，即集群A中每台服务器的待传输数据量（单位：GB）。
第3行包含m个不超过100的正整数B1,B2,…,Bm，即集群B中每台服务器所能接受的最大数据量（单位：GB）。
第 4 ~ n+3 行每行包含m个不超过100的非负整数Vi,j，表示集群A的i号服务器中每GB数据对于集群B中的j号服务器的价值。
第 n+4 ~ 2n+3 行每行包含m个不超过100的正整数Ci,j，表示集群A的i号服务器中每GB数据传输到集群B中的j号服务器所需要的开销。
输出格式
仅一行，为最大性价比。输出保留三位小数（四舍五入）。如果A的数据无法传输完毕，输出字符串 “-1”（无引号）。
样例输入
2 2
1 2
2 1
11 0
7 5
6 1
3 2
样例输出
2.091
样例解释
一个方案是：
集群A的1号服务器把所有数据传输到集群B的1号服务器，价值11，开销6。
集群A的2号服务器把1GB数据传输到集群B的1号服务器，价值7，开销3，然后把剩下的1GB数据传输到集群B的2号服务器，价值5，开销2。
性价比：(11+7+5)/(6+3+2)=2.091
另一个方案是：
集群A的1号服务器把所有数据传输到集群B的2号服务器，价值0，开销1。
集群A的2号服务器把所有数据传输到集群B的1号服务器，价值14，开销6。
性价比：(0+14)/(1+6)=2。
第一种方案更优
我的解答：
该题应该是贪心法可解，每次求性价比最高的，跟部分背包问题很像。
可惜不是，子问题不是独立的，我的解法肯定不是最优解。sign~~~，据说是最大流的问题，改天研究研究。
我的解法用了N+1个最大值堆，一个是全局所有为传输完的源站点的最高性价比方案，
其余每个源站点一个最大值堆含该站点所有传输方案。
//============================================================================
// Name : TransportOpt.cpp
// Author : Yovn
// Version :
// Copyright : yovnchine@gmail.com
//============================================================================
#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
using namespace std;
int numA;
int numB;
int* valuesA;
int* valuesB;
int** values=NULL;
int** costs=NULL;
typedef struct _HeapNode
{
int a;
int b;
float vPerC;
}HeapNode;
class MaxHeap
{
public:
MaxHeap(int n):nodes(new HeapNode[n]),total(n),len(0){
}
MaxHeap():nodes(NULL),total(0),len(0){
}
~MaxHeap()
{
delete[] nodes;
}
bool isEmpty()
{
return len<=0;
}
void setSize(int n)
{
nodes=new HeapNode[n];
total=n;
len=0;
}
HeapNode removeMax()
{
HeapNode ret=nodes[0];
nodes[0]=nodes[--len];
shift_down(0);
return ret;
}
void insert(HeapNode val)
{
nodes[len++]=val;
shift_up(len-1);
}
private :
void shift_up(int pos) {
HeapNode tmp=nodes[pos];
int index=(pos-1)/2;
while (index>=0) {
if (tmp.vPerC>nodes[index].vPerC) {
nodes[pos]=nodes[index];
pos=index;
if (pos==0)
break;
index=(pos-1)/2;
} else
break;
}
nodes[pos]=tmp;
}
void shift_down(int pos) {
HeapNode tmp=nodes[pos];
int index=pos*2+1;//use left child
while (index<len)//until no child
{
if (index+1<len&&nodes[index+1].vPerC>nodes[index].vPerC)//right child is smaller
{
index+=1;//switch to right child
}
if (tmp.vPerC<nodes[index].vPerC) {
nodes[pos]=nodes[index];
pos=index;
index=pos*2+1;
} else {
break;
}
}
nodes[pos]=tmp;
}
HeapNode* nodes;
int total;
int len;
};
void parseToInts(string& line, int* arr, int num) {
int pos=0;
for (int i=0; i<line.length(); i++) {
if (line[i]>='0'&&line[i]<='9') {
if (line[i+1]>='0'&&line[i+1]<='9') {
int a=(line[i]-'0')*10+(line[i+1]-'0');
arr[pos++]=a;
i++;
} else {
int a=(line[i]-'0');
arr[pos++]=a;
}
}
}
}
void input()
{
string line;
getline(cin,line);
sscanf(line.c_str(),"%d %d",&numA,&numB);
valuesA=new int[numA];
valuesB=new int[numB];
line.clear();
getline(cin,line);
parseToInts(line,valuesA,numA);
line.clear();
getline(cin,line);
parseToInts(line,valuesB,numB);
values=new int*[numA];
costs=new int*[numA];
for (int i=0; i<numA; i++) {
values[i]=new int[numB];
line.clear();
getline(cin, line);
parseToInts(line, values[i], numB);
}
for (int i=0; i<numA; i++) {
costs[i]=new int[numB];
line.clear();
getline(cin, line);
parseToInts(line, costs[i], numB);
}
}
bool validate() {
int sumA=0, sumB=0;
for (int i=0; i<numA; i++) {
sumA+=valuesA[i];
}
for (int i=0; i<numB; i++) {
sumB+=valuesB[i];
}
return sumA<=sumB;
}
void calc() {
MaxHeap totalHeap(numA);
MaxHeap* aHeaps=new MaxHeap[numA];
int totalC=0;
int totalV=0;
if(!validate())
{
printf("-1\n");
return;
}
for (int i=0; i<numA; i++) {
aHeaps[i].setSize(numB);
for(int j=0;j<numB;j++)
{
HeapNode node;
node.a=i;
node.b=j;
node.vPerC=(float)values[i][j]/(float)costs[i][j];
aHeaps[i].insert(node);
}
totalHeap.insert(aHeaps[i].removeMax());
}
while(!totalHeap.isEmpty())
{
HeapNode node=totalHeap.removeMax();
if(valuesA[node.a]==valuesB[node.b])
{
totalV+=values[node.a][node.b]*valuesA[node.a];
totalC+=costs[node.a][node.b]*valuesA[node.a];
valuesB[node.b]=0;
valuesA[node.a]=0;
}
else if(valuesA[node.a]>valuesB[node.b])
{
totalV+=values[node.a][node.b]*valuesB[node.b];
totalC+=costs[node.a][node.b]*valuesB[node.b];
valuesA[node.a]-=valuesB[node.b];
valuesB[node.b]=0;
}
else
{
totalV+=values[node.a][node.b]*valuesA[node.a];
totalC+=costs[node.a][node.b]*valuesA[node.a];
valuesB[node.b]-=valuesA[node.a];
valuesA[node.a]=0;
}
while(!aHeaps[node.a].isEmpty())
{
HeapNode todo=aHeaps[node.a].removeMax();
if(valuesA[todo.a]>0&&valuesB[todo.b]>0)
{
totalHeap.insert(todo);
break;
}
}
}
printf("%lf\n",(float)totalV/totalC);
}
int main() {
input();
calc();
return 0;
}