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;
}
评论