这道题貌似很多人用的是网络流 + 分层图. 这里介绍一种费用流解法.
可以证明, 最后一个人到达的时间是小于第 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 抢夺 https://darkbzoj.tk/problem/4669
唯一不同的是, 这道题的人数很大, 所以不能建分层图.
有两个显然的结论:
每天可以新到达的人数一定不降
后面的人可以跟着前面的人走, 时间相差 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;
- }
来源: http://www.bubuko.com/infodetail-3746051.html