BZOJ 2424: [HAOI2010]订货(最小费用最大流)

最小费用最大流..乱搞即可

------------------------------------------------------------------------------

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<iostream>

#include<queue>

#define rep( i, n ) for( int i = 0; i < n; ++i )

#define Rep( i, n ) for( int i = 1; i <= n; ++i )

#define clr( x, c ) memset( x, c, sizeof( x ) )

using namespace std;

const int maxn = 50 + 5;

struct edge {

int to, cap, cost;

edge *next, *rev;

};

edge *head[ maxn ], *p[ maxn ];

edge* pt;

edge EDGE[ maxn << 3 ];

void init() {

pt = EDGE;

clr( head, 0 );

}

inline void add( int u, int v, int d, int w ) {

pt->to = v;

pt->cap = d;

pt->cost = w;

pt->next = head[ u ];

head[ u ] = pt++;

}

inline void add_edge( int u, int v, int d, int w ) {

add( u, v, d, w );

add( v, u, 0, -w );

head[ u ]->rev = head[ v ];

head[ v ]->rev = head[ u ];

}

int d[ maxn ], a[ maxn ];

bool inQ[ maxn ];

int minCost( int S, int T ) {

const int inf = 0x3f3f3f3f;

int flow = 0, cost = 0;

for( ; ; ) {

clr( inQ, 0 );

clr( d, inf );

d[ S ] = 0;

inQ[ S ] = 1;

a[ S ] = inf;

queue< int > Q;

Q.push( S );

while( !Q.empty() ) {

int x = Q.front(); Q.pop();

inQ[ x ] = 0;

for( edge* e = head[ x ]; e; e = e->next )

if( e->cap > 0 && d[ e->to ] > d[ x ] + e->cost ) {

int to = e->to;

d[ to ] = d[ x ] + e->cost;

a[ to ] = min( a[ x ], e->cap );

p[ to ] = e;

if( !inQ[ to ] )

Q.push( to ), inQ[ to ] = 1;

}

if( d[ T ] == inf ) break;

flow += d[ T ];

cost += d[ T ] * a[ T ];

int x = T;

while( x != S) {

p[ x ]->cap -= a[ T ];

p[ x ]->rev->cap += a[ T ];

x = p[ x ]->rev->to;

}

return cost;

}

const int INF = 0x7fffffff;

int main() {

freopen( "test.in", "r", stdin );

int n, m, V;

cin >> n >> m >> V;

int s = 0, t = n + 1;

init();

Rep( i, n ) {

int x;

scanf( "%d", &x );

add_edge( i, t, x, 0 );

}

Rep( i, n ) {

int x;

scanf( "%d", &x );

add_edge( s, i, INF, x );

}

Rep( i, n - 1 )

add_edge( i, i + 1, V, m );

cout << minCost( s, t ) << "\n";

return 0;

}

------------------------------------------------------------------------------

2424: [HAOI2010]订货

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 603 Solved: 394
[Submit][Status][Discuss]

Description

某公司估计市场在第i个月对某产品的需求量为Ui，已知在第i月该产品的订货单价为di，上个月月底未销完的单位产品要付存贮费用m，假定第一月月初的库存量为零，第n月月底的库存量也为零，问如何安排这n个月订购计划，才能使成本最低？每月月初订购，订购后产品立即到货，进库并供应市场，于当月被售掉则不必付存贮费。假设仓库容量为S。

Input

第1行：n, m, S (0<=n<=50, 0<=m<=10, 0<=S<=10000)

第2行：U1 , U2 , ... , Ui , ... , Un (0<=Ui<=10000)

第3行：d1 , d2 , ..., di , ... , dn (0<=di<=100)

Output

只有1行，一个整数，代表最低成本

Sample Input

3 1 1000
2 4 8
1 2 4

Sample Output

HINT

Source

Day1

巴特西