60分求助

#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>

#define mid(l, r)  ( l >> 1 ) + ( r >> 1 ) + ( l & r & 1 )
#define min(a, b)  ((a) < (b) ? (a) : (b))

const int MaxN = 5 ;
const int Inf = ( 1 << 31 ) - 1 ;

int a, b ;
int ans[10] ;

struct edge
{
    int to, w, nxt ;
    edge ( )  {  }
    edge ( int to, int w, int nxt ) : to ( to ), w ( w ), nxt ( nxt ) {   }
} g[MaxN << 1] ;

int head[MaxN], ne = 1 ;
inline void Adde( int u, int v, int w )  {   g[++ ne] = edge ( v, w, head[u] ) ;  head[u] = ne ;   }

inline int Binary_search ( )
{
    static int l, r, mid ;
    l = -Inf, r = Inf ;
    while ( l ^ r )
    {
        mid = mid(l, r) ;
        mid - a < b ? l = mid + 1 : r = mid ;
    }
    return l ;
}

int fa[MaxN] ;
inline int find ( int x )
{
    while ( x ^ fa[x] )  x = fa[x] = fa[fa[x]] ;  return x ;
}

struct EDGE
{
    int u, v, w ;
    EDGE ( )  {     }
    EDGE ( int u, int v, int w ) : u ( u ), v ( v ), w ( w ) {      }
    inline short operator < ( const EDGE& rhs )  const
    {
        return w < rhs.w ;
    }
} E[MaxN];

inline int Kruskal ( )
{
    E[1] = EDGE ( 1, 2, a ) ;
    E[2] = EDGE ( 2, 3, b ) ;
    static int cnt ;
    static int ans ;
    cnt = ans = 0 ;
    std :: sort ( E + 1, E + 1 + 2 ) ;
    for ( int i = 1 ; i <= MaxN ; ++ i )  fa[i] = i ;
    for ( int i = 1 ; cnt ^ 2 ; ++ i )
    {
        int u = E[i].u, v = E[i].v ;
        int x = find ( u ), y = find ( v ) ;
        if ( x ^ y )
        {
            fa[x] = y ;
            ans += E[i].w ;
            ++ cnt ;
        }
    }
    return ans ;
}

inline int Floyd ( )
{
    static int f[MaxN][MaxN], tmp ;
    for ( int i = 1 ; i <= 3 ; ++ i )
        for ( int j = 0 ; j < 3 ; f[i][++j] = 0x3f3f3f3f ) ;
    f[1][2] = a, f[2][3] = b ;
    for ( int k = 1 ; k <= 3 ; ++ k )
        for ( int i = 1 ; i <= 3 ; ++ i )
            for ( int j = 1 ; j <= 3 ; ++ j )
                f[i][j] > ( tmp = f[i][k] + f[k][j] ) ? f[i][j] = tmp : 1 ;
    return f[1][3] ;
}

class Network_Flows
{
private:
    struct Edge
    {
        int to, nxt, w ;
        Edge ( ) { }
        Edge ( int to, int w, int nxt ) : to ( to ), w ( w ), nxt ( nxt ) {    }
    } G[MaxN << 1];

    int hhead[MaxN], nne ;
    int S, T, ret ;
    int cur[MaxN], dep[MaxN] ;

    inline void Adde( int u, int v, int w )  {   G[++ nne] = Edge ( v, w, hhead[u] ) ;  hhead[u] = nne ;   }

    inline short Bfs ( )
    {
        static int fr, tl, q[MaxN << 1] ;
        static int u, v;
        memset ( dep, 0, sizeof ( int ) * ( T + 1 ) ) ;
        fr = tl = 0 ;
        q[++ tl] = S ;
        dep[S] = 1 ;
        while ( fr ^ tl )
    {
            u = q[++ fr] ;
            for ( int i = hhead[u] ; i ; i = G[i].nxt )
        {
                v = G[i].to;
                if ( G[i].w && !dep[v] )
        {
                    dep[v] = dep[u] + 1 ;
                    q[++ tl] = v ;
                }
            }
        }
        return dep[T] != 0 ;
    }

    int Dfs ( int u, int a )
    {
        if ( u == T || !a )  return a ;
        int v, f, flow = 0 ;
        for( int& i = cur[u] ; i ; i = G[i].nxt )
    {
            v = G[i].to ;
            if ( dep[v] == dep[u] + 1 )
        {
                f = Dfs ( v, min( a - flow, G[i].w ) ) ;
                G[i].w -= f ;   G[i ^ 1].w += f ;
                flow += f ;
                if ( flow == a )  return flow ;
            }
        }
        if ( !flow )  dep[u] = -1 ; // cannot be 0;
        return flow;
    }

public:

    Network_Flows ( )
        {
        memset ( hhead, 0, sizeof hhead ) ;
        nne = 1 ;
    }

    inline void AddDbe ( int u, int v, int w )
        {
            Adde ( u, v, w ) ;  Adde ( v, u, 0 ) ;
    }
    inline int Dinic ( int S, int T )
    {
        this -> S = S, this -> T = T ;
        ret = 0 ;
        while ( Bfs ( ) )
    {
            memcpy ( cur, hhead, sizeof ( int ) * ( T + 1 ) ) ;
            ret += Dfs ( S, Inf ) ;
        }
        return ret ;
    }
} Lazer ;

inline int Spfa ( )
{
    static int dis[MaxN], tmp ;
    static short vis[MaxN] ;
    static int s = 1, t = 3, u, v ;
    static std :: deque < int > q ;
    for ( int i = 1 ; i <= t ; ++ i )  vis[i] = 0 ;
    for ( int i = 1 ; i <= t ; ++ i )  dis[i] = 0x3f3f3f3f ;
    dis[s] = 0 ;
    q.push_front ( s ) ;
    vis[s] = 1 ;
    while ( !q.empty ( ) )
    {
        u = q.front ( ) ;
        q.pop_front ( ) ;
        vis[u] = 0 ;
        for ( int i = head[u] ; i ; i = g[i].nxt )
            {
            v = g[i].to ;
            if ( dis[v] > ( tmp = dis[u] + g[i].w ) )
            {
                dis[v] = tmp ;
                if ( !vis[v] )
                {
                    ( q.empty() || dis[v] < dis[q.front()] ) ? q.push_front ( v ) : q.push_back ( v ) ;
                    vis[v] = 1 ;
                }
            }
        }
    }
    return dis[t] ;
}

class SegmentTree
{
private :
    struct node
    {
        int sum , lazy;
        short flag ;
        node *ls, *rs ;

        inline void pushdown ( int lf, int rg )
            {
            if ( flag )
            {
                ls -> flag = rs -> flag = 1 ;
                ls -> lazy = rs -> lazy = lazy ;
                flag = 0 ;
                int mid = mid(lf, rg) ;
                ls -> sum = ( mid - lf + 1 ) * lazy ;
                rs -> sum = ( rg - mid ) * lazy ;
            }
        }

        inline void update ( )
            {
            sum = ls -> sum + rs -> sum ;
        }
    } pool[MaxN << 1], *root, *tail ;

    inline void Modify ( node* &nd, int lf, int rg, int L, int R, int delta )
        {
        if ( L <= lf && rg <= R )
            {
            nd -> sum = ( lf - rg + 1 ) * delta ;
            nd -> flag = 1 ;
            nd -> lazy = delta ;
            return ;
        }
        nd -> pushdown ( lf, rg ) ;
        int mid = mid(lf, rg) ;
        if ( L <= mid )  Modify ( nd -> ls, lf, mid, L, R, delta ) ;
        if ( mid < R )  Modify ( nd -> rs, mid + 1, rg, L, R, delta ) ;
        nd -> update ( ) ;
    }

    inline int Query ( node* &nd, int lf, int rg, int L, int R )
        {
        if ( L <= lf && rg <= R )  return nd -> sum ;
        nd -> pushdown ( lf, rg ) ;
        int mid = mid(lf, rg) ;
        int rt = 0 ;
        if ( L <= mid )  rt += Query ( nd -> ls, lf, mid, L, R ) ;
        if ( mid < R )  rt += Query ( nd -> rs, mid + 1, rg, L, R ) ;
        return rt ;
    }

    inline node* _Build ( int lf, int rg )
        {
        node *nd = ++ tail ;
        nd -> sum = nd -> flag = 0 ;
        if ( lf ^ rg )
        {
            int mid = mid(lf, rg) ;
            nd -> ls = _Build ( lf, mid ) ;
            nd -> rs = _Build ( mid + 1, rg ) ;
        }
        return nd ;
    }

public :
    SegmentTree ( )
        {
        tail = pool ;
    }

    inline void Build ( int lf, int rg )
        {
        root = _Build ( lf, rg ) ;
    }
    inline void Modify ( int L, int R, int delta )
        {
        Modify ( root, 1, 5, L, R, delta ) ;
    }

    inline int Query ( int L, int R )  {
        return Query ( root, 1, 5, L, R ) ;
    }

} Seg;

namespace BIT
        {

    #define lowbit(x) ( ( x ) & ( ( ~x ) + 1 ) )

    int R[MaxN] ;

    inline void Insert ( int pos, int x )
    {
        for ( int i = pos ; i <= 3; i += lowbit(i) )  R[i] += x ;
    }

    inline int Query ( int pos )
    {
        static int rt ;
        rt = 0 ;
        for ( int i = pos ; i ; i -= lowbit(i) )  rt += R[i] ;
        return rt ;
    }
}

inline int Dp ( )
{
    static int tmp, dp[MaxN], w[MaxN], c[MaxN] ;
    w[1] = w[2] = 1 ;
    c[1] = a , c[2] = b ;
    for ( int i = 1 ; i <= 2 ; ++ i )
        for ( int j = MaxN ; j >= w[i] ; -- j )
            dp[j] < ( tmp = dp[j - w[i]] + c[i] ) ? dp[j] = tmp : 1 ;
    return dp[2] ;
}

inline void Init ( )
{
    Adde ( 1, 2, a ) ;
    Adde ( 2, 3, b ) ;
    Lazer.AddDbe ( 0, 1, Inf ) ;
    Lazer.AddDbe ( 0, 2, Inf ) ;
    Lazer.AddDbe ( 1, 3, a ) ;
    Lazer.AddDbe ( 2, 3, b ) ;
    BIT :: Insert ( 1, a ) ;
    BIT :: Insert ( 2, b ) ;
    Seg.Build ( 1, 5 ) ;
    Seg.Modify ( 1, 1, a ) ;
    Seg.Modify ( 2, 2, b ) ;
}

struct Dot
{
    int id, dis ;
    Dot ( )  {  }
    Dot ( int id, int dis ) : id ( id ), dis ( dis )  {   }
    inline short operator < ( const Dot& rhs )  const
        {
        return dis > rhs.dis ;
    }
} d[MaxN];

inline int Dijkstra ( )
{
    static std :: priority_queue < Dot > q ;
    static int dis[MaxN] ;
    static short vis[MaxN] ;
    for ( int i = 1 ; i <= MaxN ; ++ i )  dis[i] = 0x3f3f3f3f ;
    for ( int i = 1 ; i <= MaxN ; ++ i )  vis[i] = 0 ;
    q.push ( Dot ( 1, 0 ) ) ;
    vis[1] = 1 ;
    dis[1] = 0 ;
    while ( !q.empty ( ) )
    {
        int u = q.top( ).id;
        q.pop ( ) ;
        for ( int i = head[u] ; i ; i = g[i].nxt )
        {
            int v = g[i].to ;
            if ( dis[v] > dis[u] + g[i].w && !vis[v])
            {
                dis[v] = dis[u] + g[i].w ;
                q.push ( Dot ( v, dis[v] ) ) ;
                vis[v] = 1 ;
            }
        }
    }
    return dis[3] ;
}

int main ( )
{
    //freopen ( "plus.in", "r", stdin ) ;
    //freopen ( "plus.out", "w", stdout ) ;
    scanf ( "%d%d", &a, &b ) ;
    Init ( ) ;
    ans[0] = Binary_search ( ) ;
    ans[1] = Floyd ( ) ;
    ans[2] = Spfa ( ) ;
    ans[3] = BIT :: Query ( 2 ) ;
    ans[4] = Seg.Query ( 1, 2 ) ;
    ans[5] = Lazer.Dinic ( 0, 3 ) ;
    ans[6] = Dp ( ) ;
    ans[7] = Kruskal ( ) ;
    ans[8] = Dijkstra ( ) ;
    long long rt = 0 ;
    for ( int i = 0 ; i < 9 ; ++ i )    rt += ans[i] ;
    printf ( "%d\n", rt / 9 ) ;
}