请用户 @tqyaaaaang 注意,您的程序已被 hack

liu_cheng_ao 2018-06-27 17:02:24

原提交

被 hack 记录

我们为考场上数据强度过低使您通过向您致以最诚挚的歉意。

#include <bits/stdc++.h>
using namespace std;

#define LL long long
#define LD long double
#define SC(t,x) static_cast<t>(x)
#define AR(t) vector < t >
#define PII pair < int, int >
#define PLL pair < LL, LL >
#define PIL pair < int, LL >
#define PLI pair < LL, int >
#define PQ priority_queue
#define GT(type) greater < type >
#define MP make_pair
#define PB push_back
#define PF push_front
#define POB pop_back
#define POF pop_front
#define PRF first
#define PRS second
#define INIT(ar,val) memset ( ar, val, sizeof ( ar ) )
#define lp(loop,start,end) for ( int loop = start; loop < end; ++loop )
#define lpd(loop,start,end) for ( int loop = start; loop > end; --loop )
#define lpi(loop,start,end) for ( int loop = start; loop <= end; ++loop )
#define lpdi(loop,start,end) for ( int loop = start; loop >= end; --loop )
#define qmax(a,b) (((a)>(b))?(a):(b))
#define qmin(a,b) (((a)<(b))?(a):(b))
#define qabs(a) (((a)>=0)?(a):(-(a)))

const int INF = 0x3fffffff;
const int SINF = 0x7fffffff;
const long long LINF = 0x3fffffffffffffff;
const long long SLINF = 0x7fffffffffffffff;
const int MAXN = 500007;
const LD EPS = 1e-9;
const int TMS = 90;
const int MAX = SC ( int, 1e9 + 7 );

struct eT
{
	int u, v, w;
}edge[MAXN];

int n, m;
LD nw[MAXN];
int fa[MAXN], rnk[MAXN];
int ord[MAXN], op[MAXN], kp, on[MAXN], kn;

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

LL check ( LD tst );

int getfa ( int now )
{
	return fa[now] ? ( fa[now] = getfa ( fa[now] ) ) : now;
}

void uni ( int u, int v )
{
	if ( rnk[u] > rnk[v] ) swap ( u, v );
	fa[u] = v;
	if ( rnk[u] == rnk[v] ) ++rnk[v];
}



namespace task_bf
{
	int ar[MAXN], ka;
	void work ()
	{
		int ms = ( 1 << m );
		int u, v;
		LL ans = 0, cur;
		lp ( st, 0, ms ) {
			ka = 0;
			memset ( fa, 0, sizeof ( int ) * ( n + 3 ) );
			memset ( rnk, 0, sizeof ( int ) * ( n + 3 ) );
			lpi ( i, 1, m ) {
				if ( st >> ( i - 1 ) & 1 ) {
					u = edge[i].u, v = edge[i].v;
					u = getfa ( u ), v = getfa ( v );
					if ( u == v ) {
						ka = -1;
						break;
					} else {
						uni ( u, v );
						ar[++ka] = edge[i].w;
					}
				}
			}
			if ( ka == n - 1 ) {
				nth_element ( ar + 1, ar + ( n >> 1 ), ar + 1 + ka );
				cur = 0; 
				lpi ( i, 1, ka ) cur += qabs ( ar[i] - ar[n >> 1] );
				ans = qmax ( ans, cur );
			}
		}
		cout << ans << endl;
	}
}



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



void init ()
{
	// Init Everything Here

	ios::sync_with_stdio ( false );
}

void input ()
{
	// input method

	scanf ( "%d%d", &n, &m );
	lpi ( i, 1, m ) scanf ( "%d%d%d", &edge[i].u, &edge[i].v, &edge[i].w );
}

void work ()
{
	// main work

	if ( n <= 10 && m <= 20 ) {
		task_bf::work ();
		return;
	}

	sort ( edge + 1, edge + 1 + m, [] ( const eT &a, const eT &b ) { return a.w < b.w; } );

	LL ret, ans;
	LD l = 0, r = MAX, mid;
	lp ( _t, 0, TMS ) {
		mid = l + ( r - l ) / 2;
		ret = check ( mid );
		if ( ret == -1 ) l = mid;
		else if ( ret == -2 ) r = mid;
		else {
			ans = ret;
			break;
		}
	}

	cout << ans << endl;
}



LL check ( LD tst )
{
	kp = kn = 0;
	lpi ( i, 1, m ) {
		if ( edge[i].w >= tst ) op[++kp] = i, nw[i] = edge[i].w - tst;
		else on[++kn] = i, nw[i] = tst - edge[i].w;
	}
	reverse ( on + 1, on + 1 + kn );
	merge ( op + 1, op + 1 + kp, on + 1, on + 1 + kn, ord + 1, [] ( int x, int y ) { return nw[x] < nw[y]; } );

	INIT ( fa, 0 );
	INIT ( rnk, 0 );
	int i, u, v, cpn = 0, cm = 0;
	LD mini = INF, ans = 0;
	lpd ( _i, m, 0 ) {
		i = ord[_i];
		u = getfa ( edge[i].u ), v = getfa ( edge[i].v );
		if ( u ^ v ) {
			uni ( u, v );
			ans += nw[i];
			if ( edge[i].w > tst + EPS ) {
				++cpn;
				if ( cpn > 0 ) mini = nw[i];
			} else if ( edge[i].w < tst - EPS ) {
				--cpn;
				if ( cpn < 0 ) mini = nw[i];
			} else if ( cpn ) ( cpn >= 0 ) ? ++cpn : --cpn;
			else ++cpn, mini = 0;
			++cm;
			if ( cm == n - 1 ) break;
		}
	}

//	cerr << tst << " : " << cpn << " " << ans << " " << mini << endl;

	if ( cpn == 0 ) return SC ( LL, floor ( ans + 0.5 ) );
	else if ( cpn == 1 || cpn == -1 ) return SC ( LL, floor ( ans - mini + 0.5 ) );
	else return ( cpn > 0 ) ? -1 : -2;
}