首页 > Web开发 > 详细

P4400 [JSOI2008]Blue Mary的旅行

时间:2021-04-09 00:07:36      阅读:2      评论:0      收藏:0      [点我收藏+]

这道题貌似很多人用的是网络流+分层图。这里介绍一种费用流解法。

可以证明,最后一个人到达的时间是小于第100天的。

那么对于每一趟航班,如果他的起点是\(u\),终点为\(v\),可搭乘的人的数量为\(w\)。那我们就对\((u,v)\)连100条流量为\(w\),费用为\(i\)的边(\(i\)表示第几天),分别表示第\(i\)天的航班。

我们跑费用流时,也不是计算最短距离,而是找到起点到终点的一条路径上的一条费用最大的边的最小值。

比如

技术分享图片

我们要的路径是\(A \to C \to D\),因为\(max(AC,CD)<max(AB,BD)\)

跑一个流量为\(t\)的费用流即可。

#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
#define INF 0x3f3f3f3f

const int MAXN = 5005;
int flow , cost;
int n , m , u , v , w , f;
struct node{
	int v , w , f , rev;
};
vector< node > Graph[ MAXN + 5 ];

int dis[ MAXN + 5 ] , vis[ MAXN + 5 ];
int prevv[ MAXN + 5 ] , preve[ MAXN + 5 ];
void spfa( int s , int t ) {
	queue< int > Que;
	memset( dis , 0x3f , sizeof( dis ) );
	memset( vis , 0 , sizeof( vis ) );

	dis[ s ] = 0 , vis[ s ] = 1 , Que.push( s );
	while( !Que.empty( ) ) {
		int u = Que.front( );
		Que.pop( ) , vis[ u ] = 0;

		for( int i = 0 ; i < Graph[ u ].size( ) ; i ++ ) {
			int v = Graph[ u ][ i ].v , w = Graph[ u ][ i ].w;
			if( w <= dis[ u ] ) continue;	//保证一天只坐一班飞机
			if( Graph[ u ][ i ].f && dis[ v ] > max( dis[ u ] , w ) ) {
				dis[ v ] = max( dis[ u ] , w );
				prevv[ v ] = u , preve[ v ] = i;
				if( !vis[ v ] )
					Que.push( v ) , vis[ v ] = 1;
			}
		}
	}
}
void Costflow( int S , int T ) {
	while( 1 ) {
		spfa( S , T );
		if( !flow || dis[ T ] == INF ) return;
		
		int d = INF;
		for( int v = T ; v != S ; v = prevv[ v ] )
			d = min( d , Graph[ prevv[ v ] ][ preve[ v ] ].f );
		flow -= d , cost = max( cost , dis[ T ] );
		for( int v = T ; v != S ; v = prevv[ v ] ) {
			Graph[ prevv[ v ] ][ preve[ v ] ].f -=d;
			Graph[ v ][ Graph[ prevv[ v ] ][ preve[ v ] ].rev ].f += d;
		}
	}
}

int main( ) {
	scanf("%d %d %d",&n,&m,&flow);
	for( int i = 1 ; i <= m ; i ++ ) {
		scanf("%d %d %d",&u,&v,&f);
		for( int j = 1 ; j <= 105 ; j ++ ) {
			w = j;
			Graph[ u ].push_back( { v , w , f , Graph[ v ].size( ) } );
			Graph[ v ].push_back( { u , -w , 0 , Graph[ u ].size( ) - 1 } );
		}
	}
	Costflow( 1 , n );
	printf("%d\n",cost);
	return 0;
}

Update: 2021.1.5

深深的体会到 1 年前的自己太菜了。

考虑这道题的加强版:BZOJ4669 抢夺

唯一不同的是,这道题的人数很大,所以不能建分层图。

有两个显然的结论:

  • 每天可以新到达的人数一定不降

  • 后面的人可以跟着前面的人走,时间相差 1 天

但是可能过程中存在一条新的最短路,让这些跟别人走的人,通过新的最短路到达终点,这样就不会有 1 天的时差了。

所以每次增广后通过时间差值判断通过人数,无增广路之后用最大流计算。

为了保证尽量少的时间通过的人数多,用费用流增广。

这样做就不需要二分了。

如果你没有发现它是多测,就会像我一样爆零。

#include <cmath>
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define Inf 0x3f3f3f3f

const int MAXN = 1000 , MAXM = 5000;
int head[ MAXN + 5 ] , Enum = 1;
struct Edge {
	int v , nxt , flw , w;
	Edge(){}
	Edge( int V , int Nxt , int Flw , int W ) { v = V , nxt = Nxt , flw = Flw , w = W; }
} Graph[ 2 * MAXM + 5 ];
void Add_Edge( int u , int v , int flw , int c ) {
	Graph[ ++ Enum ] = Edge( v , head[ u ] , flw ,  c ); head[ u ] = Enum;
	Graph[ ++ Enum ] = Edge( u , head[ v ] , 0   , -c ); head[ v ] = Enum;
}

int dis[ MAXN + 5 ]; bool inq[ MAXN + 5 ];
int cur[ MAXN + 5 ]; bool vis[ MAXN + 5 ];
bool Spfa( int s , int t ) {
	queue< int > Que;
	memset( dis , 0x3f , sizeof( dis ) );
	memset( inq , 0 , sizeof( inq ) );
	memset( vis , 0 , sizeof( vis ) );
	memcpy( cur , head , sizeof( head ) );
	dis[ s ] = 0; Que.push( s ) , inq[ s ] = 1;
	while( !Que.empty() ) {
		int u = Que.front();  Que.pop() , inq[ u ] = 0;
		for( int i = head[ u ] ; i ; i = Graph[ i ].nxt ) {
			int v = Graph[ i ].v , flw = Graph[ i ].flw , w = Graph[ i ].w;
			if( flw && dis[ v ] > dis[ u ] + w ) {
				dis[ v ] = dis[ u ] + w;
				if( !inq[ v ] ) Que.push( v ) , inq[ v ] = 1;
			}
		}
	}
	return dis[ t ] != Inf;
}
int dfs( int u , int t , int f ) {
	if( u == t ) return f; vis[ u ] = 1;
	for( int &i = cur[ u ] ; i ; i = Graph[ i ].nxt ) {
		int v = Graph[ i ].v , flw = Graph[ i ].flw , w = Graph[ i ].w;
		if( flw && dis[ v ] == dis[ u ] + w && !vis[ v ] ) {
			int mf = dfs( v , t , min( f , flw ) );
			if( mf ) {
				Graph[ i ].flw -= mf , Graph[ i ^ 1 ].flw += mf;
				return mf;
			}
		}
	} dis[ u ] = Inf;
	return 0;
}

int n , m , k , s , t;
int main( ) {
    // freopen("snatch.in","r",stdin);
    // freopen("snatch.out","w",stdout);

    while( ~scanf("%d %d %d",&n,&m,&k) ) {
        memset( head , 0 , sizeof( head ) ); Enum = 1;

        s = 1 , t = n;
        for( int i = 1 , u , v , c ; i <= m ; i ++ ) {
            scanf("%d %d %d",&u,&v,&c);
            Add_Edge( u , v , c , 1 );
        }

        if( k == 0 ) { printf("0\n"); }
        else {
            int Maxf = 0 , last = 0;
            for( ; Spfa( s , t ) ; last = dis[ t ] ) {
                int nowf = 0; for( int fl = 0 ; ( fl = dfs( s , t , Inf ) ) != 0 ; nowf += fl );

                if( k <= ( dis[ t ] - last ) * Maxf ) { 
                    printf("%d\n", last - 1 + (int)ceil( k * 1.0 / Maxf ) ) & 0;
                    goto there;
                }

                k -= ( dis[ t ] - last ) * Maxf;
                Maxf += nowf;
            }
            if( last == 0 ) { puts( "No solution" ); goto there; }
            printf("%d\n", last - 1 + (int)ceil( k * 1.0 / Maxf ) ) & 0;
        }
        there:;
    }
    return 0;
}

P4400 [JSOI2008]Blue Mary的旅行

原文:https://www.cnblogs.com/chihik/p/P4400.html

(0)
(0)
   
举报
评论 一句话评论(0
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号