vfleaking的博客

for (int i = 1; i <= m2; i++)
{
	if (!visited[e2[i].v])
	{
		preE[e2[i].v] = NULL;
		dfs(e2[i].v);
		topE2Idx[e2[i].v] = i;
	}
	else
	{
		int t = ufs1.Find(e2[i].v);
		unionPath(e2[i].v, e2[topE2Idx[t]].v);
		isBri2[topE2Idx[t]] = isBri2[i] = false;
	}
}

#include <iostream>
#include <iomanip>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

#define ALL(a) (a).begin(), (a).end()
#define SIZE(a) (int)(a).size()

const int MaxN = 300000;
const int MaxM1 = 500000;
const int MaxM2 = 500000;

inline int getint()
{
	char c;
	while (c = getchar(), '0' > c || c > '9');

	int res = c - '0';
	while (c = getchar(), '0' <= c && c <= '9')
		res = res * 10 + c - '0';
	return res;
}

template <class T>
inline void tension(T &a, const T &b)
{
	if (b < a)
		a = b;
}

struct edge
{
	int v, u, w;
};
struct halfEdge
{
	int u, w;
	halfEdge *next;
};
halfEdge adj_pool[MaxM1 * 2], *adj_tail = adj_pool;

int n, m1, m2;
halfEdge *adj[MaxN + 1];
edge e2[MaxM2 + 1];

inline halfEdge *opposite(const halfEdge *i)
{
	return adj_pool + ((i - adj_pool) ^ 1);
}

inline void addEdge(const int &v, const int &u, const int &w)
{
	adj_tail->u = u, adj_tail->w = w;
	adj_tail->next = adj[v], adj[v] = adj_tail++;
}
inline int getE1Idx(const halfEdge *i)
{
	return ((i - adj_pool) >> 1) + 1;
}
inline edge getE1(const int &idx)
{
	edge res;
	res.v = adj_pool[(idx - 1) << 1 | 1].u;
	res.u = adj_pool[(idx - 1) << 1].u;
	res.w = adj_pool[(idx - 1) << 1].w;
	return res;
}

class UnionFindSet
{
private:
	int f[MaxN + 1];
public:
	inline void Init()
	{
		for (int i = 1; i <= n; i++)
			f[i] = i;
	}
	inline int Find(const int &v)
	{
		int res;
		for (res = v; f[res] != res; res = f[res]);
		for (int i = v, j = f[v]; i != res; f[i] = res, i = j, j = f[i]);
		return res;
	}
	inline void Union(int v, int u)
	{
		f[Find(u)] = Find(v);
	}
};

UnionFindSet ufs1, ufs2;

bool visited[MaxN + 1];
halfEdge *preE[MaxN + 1];

int topE2Idx[MaxN + 1];

bool isBri1[MaxM1 + 1], isBri2[MaxM2 + 1];

void dfs(const int &v)
{
	visited[v] = true;
	for (halfEdge *i = adj[v]; i; i = i->next)
		if (i != preE[v])
		{
			if (!visited[i->u])
			{
				preE[i->u] = opposite(i);
				dfs(i->u);
				ufs1.Union(v, i->u);
			}
			else
			{
				int cur = ufs2.Find(v);
				while (ufs2.Find(cur) != ufs2.Find(i->u))
				{
					isBri1[getE1Idx(preE[cur])] = false;
					ufs2.Union(preE[cur]->u, cur);
					cur = ufs2.Find(cur);
				}
				isBri1[getE1Idx(i)] = false;
			}
		}
}

inline double unionPath(int v, int u)
{
	static bool book[MaxN + 1];

	v = ufs2.Find(v), u = ufs2.Find(u);

	int tv = v, tu = u;
	while (tv != tu && !book[tv] && !book[tu])
	{
		if (preE[tv])
			book[tv] = true, tv = ufs2.Find(preE[tv]->u);
		if (preE[tu])
			book[tu] = true, tu = ufs2.Find(preE[tu]->u);
	}
	int lca = book[tv] ? tv : tu;

	for (int i = v; i != tv; i = ufs2.Find(preE[i]->u))
		book[i] = false;
	book[tv] = false;
	for (int i = u; i != tu; i = ufs2.Find(preE[i]->u))
		book[i] = false;
	book[tu] = false;

	double res = 0.0;
	for (int i = v; i != lca; i = ufs2.Find(i))
	{
		isBri1[getE1Idx(preE[i])] = false;
		res += preE[i]->w;
		ufs2.Union(preE[i]->u, i);
	}
	for (int i = u; i != lca; i = ufs2.Find(i))
	{
		isBri1[getE1Idx(preE[i])] = false;
		res += preE[i]->w;
		ufs2.Union(preE[i]->u, i);
	}

	return res;
}

int main()
{
	freopen("2307.in", "r", stdin);
	freopen("2307.out", "w", stdout);

	cin >> n >> m1 >> m2;
	for (int i = 1; i <= m1; i++)
	{
		int v = getint(), u = getint(), w = getint();
		// ((1, v), (1, u), w)
		addEdge(v, u, w);
		addEdge(u, v, w);
	}

	for (int i = 1; i <= m2; i++)
	{
		e2[i].v = getint(), e2[i].u = getint(), e2[i].w = getint();
		// ((1, v), (2, u), w)
	}

	ufs1.Init();
	ufs2.Init();

	fill(isBri1 + 1, isBri1 + m1 + 1, true);
	fill(isBri2 + 1, isBri2 + m2 + 1, true);

	double res = 0.0;
	for (int i = 1; i <= m2; i++)
	{
		if (!visited[e2[i].v])
		{
			preE[e2[i].v] = NULL;
			dfs(e2[i].v);
			topE2Idx[e2[i].v] = i;
		}
		else
		{
			int t = ufs1.Find(e2[i].v);
			unionPath(e2[i].v, e2[topE2Idx[t]].v);
			isBri2[topE2Idx[t]] = isBri2[i] = false;
		}
	}
	
	// adjacency table of two adjacent layers
	static vector<int> adjB[MaxN + 1];
	static int onlyU[MaxN + 1];
	for (int i = 1; i <= m2; i++)
		adjB[ufs1.Find(e2[i].v)].push_back(ufs2.Find(e2[i].u));

	int valid_n = 0;
	static int valid[MaxN];
	for (int v = 1; v <= n; v++)
		if (v == ufs1.Find(v))
		{
			sort(ALL(adjB[v]));
			adjB[v].erase(unique(ALL(adjB[v])), adjB[v].end());

			if (SIZE(adjB[v]) > 1)
				valid[valid_n++] = v;
			if (SIZE(adjB[v]) == 1)
				onlyU[v] = adjB[v][0];
			else
				onlyU[v] = 0;
		}

	for (double coe = 1.0; valid_n > 0; coe *= 0.9)
	{
		static vector<int> backup[MaxN + 1];
		for (int i = 0; i < valid_n; i++)
		{
			int v = valid[i];
			for (vector<int>::iterator pu = adjB[v].begin(); pu != adjB[v].end(); pu++)
				backup[v].push_back(ufs1.Find(*pu));
		}

		for (int i = 0; i < valid_n; i++)
		{
			int v = valid[i];

			int u1 = adjB[v][0];
			int idx1 = topE2Idx[ufs1.Find(u1)];
			if (isBri2[idx1])
			{
				isBri2[idx1] = false;
				res += (10 - 9 * coe) * e2[idx1].w;
			}

			for (int j = 1; j < SIZE(adjB[v]); j++)
			{
				int u2 = adjB[v][j];
				int idx2 = topE2Idx[ufs1.Find(u2)];

				if (ufs1.Find(u1) != ufs1.Find(u2))
				{
					ufs1.Union(u1, u2);
					ufs2.Union(e2[idx1].v, e2[idx2].v);

					if (isBri2[idx2])
					{
						isBri2[idx2] = false;
						res += (10 - 9 * coe) * e2[idx2].w;
					}
				}
				res += (10 - 9 * coe) * unionPath(u1, u2);
			}
		}

		static int cnt[MaxN + 1];
		for (int i = 0; i < valid_n; i++)
		{
			int v = valid[i];
			onlyU[v] = ufs2.Find(adjB[v][0]);
			cnt[ufs1.Find(onlyU[v])]++;
			adjB[v].clear();
		}

		int tvalid_n = 0;
		for (int i = 0; i < valid_n; i++)
		{
			int v = valid[i];

			for (vector<int>::iterator pu = backup[v].begin(); pu != backup[v].end(); pu++)
				if (onlyU[*pu])
					adjB[ufs1.Find(onlyU[v])].push_back(ufs2.Find(onlyU[*pu]));
			backup[v].clear();

			int cur = ufs1.Find(onlyU[v]);
			if (--cnt[cur] == 0)
			{
				sort(ALL(adjB[cur]));
				adjB[cur].erase(unique(ALL(adjB[cur])), adjB[cur].end());

				if (SIZE(adjB[cur]) > 1)
					valid[tvalid_n++] = cur;
				else if (SIZE(adjB[cur]) == 1)
					onlyU[cur] = adjB[cur][0];
			}
		}

		valid_n = tvalid_n;
	}

	for (int i = 1; i <= m1; i++)
		if (isBri1[i])
			res += 10 * getE1(i).w;
	for (int i = 1; i <= m2; i++)
		if (isBri2[i])
			res += 10 * e2[i].w;

	cout << fixed << setprecision(2) << res << endl;

	return 0;
}