BZOJ 1221: [HNOI2001] 软件开发(最小费用最大流)

不知道为什么这么慢....

费用流,拆点....

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

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<iostream>

#include<queue>

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

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

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

using namespace std;

const int maxn = 2000 + 5;

struct edge {

int to, cap, cost;

edge *next, *rev;

};

edge EDGE[ maxn << 3 ];

edge* pt;

edge* head[ maxn ];

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 ];

}

edge* p[ maxn ];

int d[ maxn ], a[ maxn ];

bool inQ[ maxn ];

const int INF = 0x3f3f3f3f;

int minCost( int S, int T ) {

int cost = 0;

for( ; ; ) {

clr( d, INF );

clr( inQ, 0 );

queue< int > Q;

d[ S ] = 0, a[ S ] = INF, 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( d[ e -> to ] > d[ x ] + e -> cost && e -> cap > 0 ) {

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;

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;

}

int main() {

init();

int n, a, b, f[ 3 ];

cin >> n >> a >> b;

rep( i, 3 ) cin >> f[ i ];

int s = 0, t = n * 2 + 1;

Rep( i, n ) {

int x;

scanf( "%d", &x );

add_edge( s, i, x, 0 );

add_edge( s, i + n, INF, f[ 0 ] );

add_edge( i + n, t, x, 0 );

}

Rep( i, n - 1 )

add_edge( i, i + 1, INF, 0 );

for( int i = 1; i + a + 1 <= n; i++ )

add_edge( i, i + a + n + 1, INF, f[ 1 ]);

for( int i = 1; i + b + 1 <= n; i++ )

add_edge(i, i + b + n + 1, INF, f[ 2 ] );

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

return 0;

}

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

1221: [HNOI2001] 软件开发

Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 820 Solved: 449
[Submit][Status][Discuss]

Description

某软件公司正在规划一项n天的软件开发计划，根据开发计划第i天需要ni个软件开发人员，为了提高软件开发人员的效率，公司给软件人员提供了很多的服务，其中一项服务就是要为每个开发人员每天提供一块消毒毛巾，这种消毒毛巾使用一天后必须再做消毒处理后才能使用。消毒方式有两种，A种方式的消毒需要a天时间，B种方式的消毒需要b天（b>a），A种消毒方式的费用为每块毛巾fA, B种消毒方式的费用为每块毛巾fB，而买一块新毛巾的费用为f（新毛巾是已消毒的，当天可以使用）；而且f>fA>fB。公司经理正在规划在这n天中，每天买多少块新毛巾、每天送多少块毛巾进行A种消毒和每天送多少块毛巾进行B种消毒。当然，公司经理希望费用最低。你的任务就是：为该软件公司计划每天买多少块毛巾、每天多少块毛巾进行A种消毒和多少毛巾进行B种消毒，使公司在这项n天的软件开发中，提供毛巾服务的总费用最低。

Input

第1行为n,a,b,f,fA,fB. 第2行为n1，n2，……，nn. （注：1≤f,fA,fB≤60，1≤n≤1000）

Output

最少费用

Sample Input

4 1 2 3 2 1
8 2 1 6

Sample Output

HINT

Source

最小费用最大流

巴特西