不知道為什么這么慢....

費用流,拆點....

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

#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] 軟件開發(fā)

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

Description

某軟件公司正在規(guī)劃一項n天的軟件開發(fā)計劃，根據(jù)開發(fā)計劃第i天需要ni個軟件開發(fā)人員，為了提高軟件開發(fā)人員的效率，公司給軟件人員提供了很多的服務(wù)，其中一項服務(wù)就是要為每個開發(fā)人員每天提供一塊消毒毛巾，這種消毒毛巾使用一天后必須再做消毒處理后才能使用。消毒方式有兩種，A種方式的消毒需要a天時間，B種方式的消毒需要b天（b>a），A種消毒方式的費用為每塊毛巾fA, B種消毒方式的費用為每塊毛巾fB，而買一塊新毛巾的費用為f（新毛巾是已消毒的，當(dāng)天可以使用）；而且f>fA>fB。公司經(jīng)理正在規(guī)劃在這n天中，每天買多少塊新毛巾、每天送多少塊毛巾進行A種消毒和每天送多少塊毛巾進行B種消毒。當(dāng)然，公司經(jīng)理希望費用最低。你的任務(wù)就是：為該軟件公司計劃每天買多少塊毛巾、每天多少塊毛巾進行A種消毒和多少毛巾進行B種消毒，使公司在這項n天的軟件開發(fā)中，提供毛巾服務(wù)的總費用最低。

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

38

HINT

Source

最小費用最大流

?

轉(zhuǎn)載于:https://www.cnblogs.com/JSZX11556/p/4524579.html

總結(jié)

以上是生活随笔為你收集整理的BZOJ 1221: [HNOI2001] 软件开发(最小费用最大流)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。