不知道为什么这么慢....
费用流,拆点....
--------------------------------------------------------------------------------
#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
8 2 1 6
Sample Output
38