最短路

P2662 牛场围栏

求出最大无法组成的围栏长度.

  • 如果有长度为1的木料,那显然任何长度都能组成
  • 没有长度为1的木料.假设长度最短的木料长度为$L$ , 那么无法组成的长度一定可以表示为 $k * L + i , 0 \leq k , 0 \leq i \leq L - 1$ ,我们把模$L$得到的$L$个数抽象为$L$个点,利用最短路,$dis[i], 0 \leq i \leq L - 1 $ 表示组成长度模$L$为$i$的围栏所需要的最小长度,初始$dis[0] = 0$ , 其他为$inf$ , 用 $dis[(i+len)%L] = min( dis[(i+len)%L] , dis[i] + len )$ 来不断更新 , 即是每个木料也都抽象为一条边,木料的长度为边权。得到这个$dis$数组有什么用呢?

1.

如果$dis[i] != inf$ , 说明可以组成长度模$L$为i的围栏,且所需木料的最短长度为$dis[i]$ , 既然长度为$dis[i]$的围栏能够组成,那么所有的长度为$dis[i] + k * L (0 leq k) $的围栏也都能组成。并且我们也可以发现,长度为$dis[i] - k * L$ 的围栏我们都无法组成,因为一旦长度为$dis[i] - k * L$ 的围栏能够组成,并且$dis[i] - k * L < dis[i]$ , 那显然组成长度模L为i的围栏所需的最短木料就不是$dis[i]$ , 而是$dis[i] - k * L$了,因此$ max(dis[i]) - L $就是我们无法组成的最大 围栏长度。

2.

如果出现某个$dis[i]$为$inf$,即是所有长度模$L$为$i$的围栏都无法组成,那就没有最大值可言了,答案就是 -1.

用SPFA跑最短路即可。

#include<bits/stdc++.h>

#define ls (rt << 1)
#define rs (rt << 1 | 1)
#define lowbit( x ) (x&(-x))
#define SZ( v ) ((int)(v).size())
#define All( v ) (v).begin(), (v).end()
#define mp( x , y ) make_pair(x,y)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair < int , int > P;
const int N = 3e3 + 10;
const int M = 1e7 + 10;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const int INF = 2e9;
const int seed = 131;
int n , m , a[N] , vis[N] , vis1[N] , tot , dis[N] , mn = inf;
queue < int > Q;

void spfa () {
    memset ( dis , inf , sizeof ( dis ) );
    dis[0] = 0;
    Q.push ( 0 );
    vis1[0] = 1;
    while ( ! Q.empty () ) {
        int u = Q.front ();
        Q.pop ();
        vis1[u] = 0;
        for ( int i = 1 ; i <= tot ; ++ i ) {
            int v = ( a[i] + u ) % mn;
            if ( dis[v] > dis[u] + a[i] ) {
                dis[v] = dis[u] + a[i];
                if ( ! vis1[v] ) Q.push ( v ) , vis1[v] = 1;
            }
        }
    }
    int ans = 0;
    for ( int i = 1 ; i < mn ; ++ i ) ans = max ( ans , dis[i] );
    printf ( "%d\n" , ans == inf ? - 1 : ans - mn );
}

int main () {
    int x;
    scanf ( "%d%d" , &n , &m );
    for ( int i = 1 ; i <= n ; ++ i ) {
        scanf ( "%d" , &x );
        for ( int j = 0 ; j <= m ; ++ j ) {
            if ( x - j > 0 && ! vis[x - j] ) {
                vis[x - j] = 1;
                a[++ tot] = x - j;
                mn = min ( mn , x - j );
            }
        }
    }
    if ( vis[1] ) return 0 * puts ( "-1" );
    spfa ();
    return 0;
}
Last modification:March 20th, 2020 at 12:31 am
如果觉得我的文章对你有用,请随意赞赏