60分求助
查看原帖
60分求助
349808
蜀都客车楼主2021/2/27 20:36
#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 ) ;
}
2021/2/27 20:36
加载中...