tqyaaaaang's Blog

UOJ - 126 - 快餐店 ( 环套树DP )

UOJ - 126 - 快餐店 ( 环套树DP )

题目链接:http://uoj.ac/problem/126

详细题解在代码后面

思路

环套树DP(废话)

考虑树的情况怎么做

考虑如何拓展到环上

代码

#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>

#include <cstdio>
#include <cstdlib>
#include <cmath>

#include <vector>
#include <deque>
#include <list>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <bitset>
#include <algorithm>
#include <numeric>
#include <utility>

#include <string>
#include <cstring>

using namespace std;

#define LL long long
#define LD double
#define SC(tp,var) static_cast < tp > ( var )
#define AR(tp) vector < tp >
#define PII pair < int, int >
#define PIL pair < int, long long >
#define PLI pair < long long, int >
#define PLL pair < long long, long long >
#define MP make_pair
#define FF first
#define SS second
#define PB push_back
#define PF push_front
#define POB pop_back
#define POF pop_front
#define PQ priority_queue
#define INIT(var,val) memset ( var, val, sizeof ( var ) )
#define fo(fname) freopen ( fname ".in", "r", stdin ); freopen ( fname ".out", "w", stdout );
#define lp(lpvar,lpst,lpen) for ( int lpvar = lpst, _lpen = lpen; lpvar < _lpen; ++lpvar )
#define lpi(lpvar,lpst,lpen) for ( int lpvar = lpst, _lpen = lpen; lpvar <= _lpen; ++lpvar )
#define lpd(lpvar,lpst,lpen) for ( int lpvar = lpst, _lpen = lpen; lpvar > _lpen; --lpvar )
#define lpdi(lpvar,lpst,lpen) for ( int lpvar = lpst, _lpen = lpen; lpvar >= _lpen; --lpvar )
#define qmax(a,b) (((a)<(b))?(b):(a))
#define qmin(a,b) (((a)<(b))?(a):(b))
#define qabs(a) (((a)<0)?(-(a)):(a))
#define qsqr(a) ((a)*(a))

const int INF = 0x3fffffff;
const int SINF = 0x7fffffff;
const long long LINF = 0x3fffffffffffffffLL;
const long long SLINF = 0x7fffffffffffffffLL;
const int MINF = 0x3f3f3f3f;
const LD DINF = pow ( 2, 100 );
const int MAXN = 200007;
const LL MAXANS = SC ( LL, 2e14 + 7 );

struct eT
{
	void setd ( int _u, int _v, int _w, int _l )
	{
		u = _u, v = _v, w = _w, last = _l;
	}
	
	int u, v, w, last;
}edge[MAXN];

struct evT
{
	void setd ( LL _t, int _d )
	{
		t = _t, del = _d;
	}
	
	bool operator < ( const evT &a ) const
	{
		return t < a.t;
	}
	
	LL t;
	int del;
}ev[MAXN*4];

int n;
int kv;
LL ans;
int ke, la[MAXN];
int cyc[MAXN], kc, cw[MAXN];
LL ps[MAXN], clen;
int ci[MAXN];
bool vis[MAXN], ins[MAXN];
int stk[MAXN], top;
LL ml[MAXN];
int qn[MAXN], qx[MAXN];



void init ();
void input ();
void work ();

void findcyc ( int now, int fa );
LL dfs1 ( int now, int fa );
int getw ( int u, int v );
void dfs2 ( int now, int fa, int fw, LL ad );



int main ()
{
	init ();
	input ();
	work ();
}



void init ()
{
	ios::sync_with_stdio ( false );
	cin.tie ( 0 );
	
//	fo ( "foodshop" );
}

void input ()
{
	scanf ( "%d", &n );
	int u, v, w;
	INIT ( la, -1 );
	lp ( i, 0, n ){
		scanf ( "%d%d%d", &u, &v, &w ); w *= 2;
		edge[ke].setd ( u, v, w, la[u] );
		la[u] = ke++;
		edge[ke].setd ( v, u, w, la[v] );
		la[v] = ke++;
	}
}

void work ()
{
	findcyc ( 1, -1 );
	if ( !kc ){   // self-loop
		lp ( i, 0, n ) if ( edge[i<<1].u == edge[i<<1].v ) cyc[++kc] = edge[i<<1].u, ci[edge[i<<1].u] = 1;
	}
	
	clen = 0;
	lpi ( i, 1, kc ){
		dfs1 ( cyc[i], -1 );
		cyc[i+kc] = cyc[i];
		cw[i+kc] = cw[i] = getw ( cyc[i], cyc[i+1] );
		clen += cw[i];
	}
	lpi ( i, 1, kc<<1 ) ps[i] = ps[i-1] + cw[i-1];
	
//	lpi ( i, 1, kc ) cerr << cyc[i] << " "; cerr << endl;
//	lpi ( i, 1, kc ) cerr << ps[i] << " "; cerr << endl;
	
	LL mini = LINF;
	int nl = 1, nr = 0, xl = 1, xr = 0;
	lpi ( i, 1, kc ){
		while ( nl <= nr && ml[cyc[i]] - ps[i] >= ml[cyc[qn[nr]]] - ps[qn[nr]] ) --nr;
		qn[++nr] = i;
		while ( xl <= xr && ml[cyc[i]] + ps[i] >= ml[cyc[qx[xr]]] + ps[qx[xr]] ) --xr;
		qx[++xr] = i;
	}
	lpi ( i, kc+1, kc<<1 ){
		if ( nl <= nr && qn[nl] == i - kc ) ++nl;
		if ( xl <= xr && qx[xl] == i - kc ) ++xl;
		while ( xl <= xr && qx[xl] < qn[nl] ) ++xl;
		while ( xl <= xr && ml[cyc[i]] + ps[i] >= ml[cyc[qx[xr]]] + ps[qx[xr]] ) --xr;
		qx[++xr] = i;
		while ( nl <= nr && ml[cyc[i]] - ps[i] >= ml[cyc[qn[nr]]] - ps[qn[nr]] ) --nr;
		qn[++nr] = i;
//		cerr << i << " " << q[l] << endl;
		if ( qabs ( ml[cyc[qx[xl]]] - ml[cyc[qn[nl]]] ) <= ps[qx[xl]] - ps[qn[nl]] ) mini = min ( mini, ml[cyc[qx[xl]]] + ps[qx[xl]] + ml[cyc[qn[nl]]] - ps[qn[nl]] );
	}
//	cerr << mini << endl;
	ans = mini >> 1;
	
	LL maxi = -LINF;
	int mp = -1;
	lpi ( i, 1, kc ){
		if ( ml[cyc[i]] > maxi ){
			maxi = ml[cyc[i]];
			mp = i;
		}
	}
	LL cmx = -LINF;
	LL ndist;
	lpi ( i, 1, kc ){
		if ( i ^ mp ){
			ndist = qabs ( ps[mp] - ps[i] );
			cmx = max ( cmx, qmin ( ndist, clen - ndist ) + ml[cyc[i]] );
		}
	}
//	cerr << maxi << " " << mp << " " << cmx << endl;
	dfs2 ( cyc[mp], -1, 0, cmx );
	
	printf ( "%.1lf\n", SC ( double, ans ) / 2 );
}



void findcyc ( int now, int fa )
{
	if ( vis[now] ){
		if ( ins[now] ){
			stk[top] = -1;
			while ( stk[top] ^ now ){
				--top;
				cyc[++kc] = stk[top];
				ci[stk[top]] = kc;
				ins[stk[top]] = false;
			}
		}
		return;
	}
	vis[now] = ins[now] = true;
	stk[top++] = now;
	for ( int i = la[now]; ~i; i = edge[i].last ) if ( edge[i].v ^ fa ) findcyc ( edge[i].v, now );
	if ( ins[now] ) --top, ins[now] = false;
}

LL dfs1 ( int now, int fa )
{
	ml[now] = 0;
	for ( int i = la[now]; ~i; i = edge[i].last ){
		if ( ( edge[i].v ^ fa ) && !ci[edge[i].v] ){
			ml[now] = max ( ml[now], dfs1 ( edge[i].v, now ) + edge[i].w );
		}
	}
	return ml[now];
}

int getw ( int u, int v )
{
	for ( int i = la[u]; ~i; i = edge[i].last ){
		if ( edge[i].v == v ) return edge[i].w;
	}
	return INF;
}

void dfs2 ( int now, int fa, int fw, LL ad )
{
	if ( qabs ( ( ad - fw ) - ml[now] ) <= fw ) ans = min ( ans, ( ml[now] + ad ) >> 1 );
	ans = min ( ans, qmax ( ml[now], ad ) );
	int v;
	LL maxi = -LINF, sm = -LINF, nv;
	for ( int i = la[now]; ~i; i = edge[i].last ){
		v = edge[i].v;
		if ( ( v ^ fa ) && !ci[v] ){
			nv = ml[v] + edge[i].w;
			if ( nv > maxi ) sm = maxi, maxi = nv;
			else if ( nv > sm ) sm = nv;
		}
	}
	for ( int i = la[now]; ~i; i = edge[i].last ){
		v = edge[i].v;
		if ( ( v ^ fa ) && !ci[v] ){
			dfs2 ( v, now, edge[i].w, max ( ad, ( ( ml[v] + edge[i].w ) ^ maxi ) ? maxi : sm ) + edge[i].w );
		}
	}
}

题解

首先把环找出来之后,对每个子树跑DP。

然后发现选的可以在子树里也可以在环上。子树里的话直接肯定在最深的那个子树里,再跑一遍DP就行了。

关键是环上怎么处理。一种思路是二分答案,然后变成环上的是否有位置被所有区间覆盖的问题,可以 \(O(n \log^2 n)\) 做。把排序改成基数排序可以做到 \(O(n \log n)\),在UOJ上就可以过。。。

但是这种做法并不优美。我们考虑一种选择位置的方案,以及所有点连到对应方案的路径,可以发现环上一定有至少一条边不会经过。我们把这条边断掉就变成了树。树的情况直接就是直径的一半,非常好做。那么环上我们把环翻倍成链之后枚举切的是哪一条边,设环上一个点子树深度是 \(depth[i]\),链上的位置是 \(pos[i]\),环长是 \(K\),然后求最长链就变成了求变成一个求一个区间的 \(depth[r]+pos[r]+depth[l]-depth[l]\) 满足 \((i \le l \le r \le i+K-1)\) 的最大值,最优解就是 \(1 \le i \le K\) 的最小值,分别对 \(depth[i]+pos[i]\) 和 \(depth[i]-pos[i]\) 维护单调队列即可。(不用考虑 \(l > r\) 的情况,因为把 \(l\) 和 \(r\) 交换一下一定更大。于是我们就可以 \(O(n)\) 的做这题了。

Tianqi Yang

View Comments
Navigation