NC25226. Money
描述
MINIEYE has n factories around the world and each factory will manufacture different product models according to the manufacture plan. Factory i plans to begin production at day li and end at day ri, including the begin and the end day, so total production time is (ri-li+1) days. The factory needs to bring in ki devices before the lith day to begin production.
The devices can be purchased locally or borrowed and transported from other factories. The price of the devices varies in different regions.
Each device will cost ai RMB if factory i purchases it locally.
If factory i plans to borrow some devices from another MINIEYE factory, say factory i wants to borrow x devices from factory j, first, factory j must have completed all the manufacture tasks, so rj < li, because devices must be ready before lith day; second, there must be a route between factory i and factory j, and all the routes will be given in the input; finally, factory i needs to pay x × dis(i, j) RMB for the transportation. Note that, factory i can only purchase or borrow devices before day li, and once it has ki devices it cannot purchase or borrow any more.
M is responsible for manufacturing, and he needs your help to figure out the minimum cost of money to complete all manufacture tasks on time as scheduled.
输入描述
The first line contains two integers n, m(1 ≤ n ≤ 50).
For the following n lines, the ith line contains four integers l, r, k, a(1 ≤ li < ri ≤ 107, 1 ≤ ki, ai ≤ 107).
For the following m lines, the ith line contains two integers ui, vi, wi(1 ≤ ui, vi ≤ n, 1 ≤ wi ≤ 107), describing an undirected edge between ui and vi with cost wi per device.
输出描述
Output the minimum cost in a single line.
示例1
输入:
5 4 1 2 10 1 4 7 20 4 3 6 5 10 1 3 3 2 3 5 3 7 1 2 2 2 3 4 1 3 7 4 5 3
输出:
137
C++11(clang++ 3.9) 解法, 执行用时: 18ms, 内存消耗: 740K, 提交时间: 2019-04-23 22:31:58
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 100 + 10;
const ll inf = 0x3f3f3f3f3f3f3f3f;
struct Edge { int from, to; ll cap, flow, cost; };
struct MCMF
{
int n, m;
vector<Edge> edges;
vector<int> G[maxn];
bool inq[maxn];
ll dis[maxn], path[maxn], a[maxn];
void init(int n)
{
this -> n = n;
for(int i = 0; i <= n; i++) G[i].clear();
edges.clear();
}
void addEdge(int from, int to, ll cap, ll cost)
{
edges.push_back(Edge{from, to, cap, 0, cost});
edges.push_back(Edge{to, from, 0, 0, -cost});
m = edges.size();
G[from].push_back(m - 2);
G[to].push_back(m - 1);
}
bool Bellman_Ford(int s, int t, ll& flow, ll &cost)
{
for(int i = 0; i <= n; i++) dis[i] = inf;
memset(inq, 0, sizeof inq);
dis[s] = 0, inq[s] = true, path[s] = 0, a[s] = inf;
queue<int> Q;
Q.push(s);
while(!Q.empty())
{
int u = Q.front(); Q.pop();
inq[u] = false;
for(int i = 0; i < G[u].size(); i++)
{
Edge& e = edges[G[u][i]];
if(e.cap > e.flow &&dis[e.to] > dis[u] + e.cost)
{
dis[e.to] = dis[u] + e.cost;
path[e.to] = G[u][i];
a[e.to] = min(a[u], e.cap - e.flow);
if(!inq[e.to])
{
Q.push(e.to);
inq[e.to] = true;
}
}
}
}
if(dis[t] == inf) return false;
flow += a[t];
cost += dis[t] * a[t];
for(int u = t; u != s; u = edges[path[u]].from)
{
edges[path[u]].flow += a[t];
edges[path[u]^1].flow -= a[t];
}
return true;
}
ll mincostMaxFlow(int s, int t)
{
ll flow = 0, cost = 0;
while(Bellman_Ford(s, t, flow, cost));
return cost;
}
}ans;
int l[maxn], r[maxn];
ll k[maxn], a[maxn], dis[maxn][maxn];
int main()
{
int n, m, u, v, w;
scanf("%d%d", &n, &m);
memset(dis, inf, sizeof dis);
for(int i = 1; i <= n; i++)
{
scanf("%d%d%lld%lld", &l[i], &r[i], &k[i], &a[i]);
dis[i][i] = 0;
}
while(m--)
{
scanf("%d%d%d", &u, &v, &w);
dis[u][v] = dis[v][u] = w;
}
for(int k = 1; k <= n; k++)
for(int j = 1; j <= n; j++)
for(int i = 1; i <= n; i++)
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
int S = 0, T = 2 * n + 1;
ans.init(T);
for(int i = 1; i <= n; i++)
{
ans.addEdge(S, i, k[i], 0);
ans.addEdge(i + n, T, k[i], 0);
ans.addEdge(S, i + n, inf, a[i]);
for(int j = 1; j <= n; j++)
if(r[i] < l[j]) ans.addEdge(i, j + n, inf, dis[i][j]);
}
printf("%lld\n", ans.mincostMaxFlow(S, T));
return 0;
}