Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
tree: df2ccef693
Fetching contributors…

Cannot retrieve contributors at this time

127 lines (114 sloc) 3.713 kb
#include "../Headers/models.h"
#include "../Headers/order.h"
#include "../Headers/elevator.h"
#include "../Headers/emulator.h"
#include <cstring>
typedef list<Order*>::iterator OrderIter;
#define MAXN 500 /* 最大点的个数 */
#define order_s Emulator::orders.begin()
#define order_e Emulator::orders.end()
#define ele_s Emulator::elevators.begin()
#define ele_e Emulator::elevators.end()
int S, T; /* 源点和汇点 */
int flow[MAXN][MAXN], cost[MAXN][MAXN];
int path[MAXN];
int inq[MAXN], Q[MAXN], dist[MAXN];
/*
* 称某电梯对某order顺路,当且仅当该电梯闲置 (如果我们的电梯知道更加多的事情,可以有更加多的算法)
* 电梯到达order的经过的楼层数目是电梯i到达楼层j的代价
* 构图做最小费用最大流,以保证在当前情况下满足最多数量的order并且总代价最小
*/
void addEdge(int a, int b, int f, int c)
{
flow[a][b] = f, flow[b][a] = 0;
cost[a][b] = c, cost[b][a] = -c;
}
int BytheWay(Elevator *ele, Order *order)
{
if (ele->Get_nPassenger() == Elevator::Get_capacity())
return 0;
if (ele->Dir() == '-' && ele->Get_nPassenger() == 0 && ele->Get_inst()->size() == 0)
return 1;
else return 0;
}
int spfa()
{
memset(dist, -1, sizeof(dist));
memset(inq, 0, sizeof(inq));
inq[S] = 1;
dist[S] = 0;
memset(path, -1, sizeof(path));
Q[0] = S;
for (int h = 0, t = 0; h <= t; ++ h)
{
int cur = Q[h];
for (int nxt = S; nxt <= T; ++ nxt)
if (flow[cur][nxt] == 1 && (dist[nxt] == -1 || dist[nxt] > dist[cur] + cost[cur][nxt]))
{
dist[nxt] = dist[cur] + cost[cur][nxt];
path[nxt] = cur;
if (inq[nxt]) continue;
inq[Q[++ t] = nxt] = 1;
}
inq[cur] = 0;
}
return path[T] != -1;
}
void Controller::CostFLow()
{
memset(flow, 0, sizeof(flow));
memset(cost, 0, sizeof(cost));
S = 0, T = Emulator::orders.size() + Emulator::elevators.size() + 1;
int idx_order, idx_ele;
idx_order = 0;
for (OrderIter iter = order_s; iter != order_e; ++ iter)
addEdge(S, ++ idx_order, 1, 0);
idx_order = 0;
for (OrderIter iter = order_s; iter != order_e; ++ iter)
{
++ idx_order;
idx_ele = Emulator::orders.size();
for (EleIter jter = ele_s; jter != ele_e; ++ jter)
{
++ idx_ele;
if (BytheWay(*jter, *iter))
addEdge(idx_order, idx_ele, 1, abs((*jter)->Get_pos() - (*iter)->from));
//addEdge(idx_order, idx_ele, 1, estimate(*jter, *iter));
}
}
idx_ele = Emulator::orders.size();
for (EleIter iter = ele_s; iter != ele_e; ++ iter)
addEdge(++ idx_ele, T, 1, 0);
int tt = 0;
while (spfa())
{
++ tt;
/* Every path flow could only be one */
for (int i = T; i != S; i = path[i])
flow[path[i]][i] = 0, flow[i][path[i]] = 1;
/* No need to calc the mincost */
}
printf("%u %u\n", Emulator::orders.size(), tt);
//if (! tt) return;
//memset(toDel, 0, sizeof(toDel));
idx_order = 0;
for (OrderIter iter = order_s; iter != order_e; )
{
++ idx_order;
int flag = 0;
idx_ele = Emulator::orders.size();
for (EleIter jter = ele_s; jter != ele_e; ++ jter)
{
++ idx_ele;
if (flow[idx_ele][idx_order] == 1)
{
(*jter)->PushInst(new Instruction((*iter)->from, 1));
flag = 1;
break;
}
}
OrderIter temp = iter ++;
if (flag)
Emulator::orders.erase(temp);
}
}
Jump to Line
Something went wrong with that request. Please try again.