给定带权无向图，求最大 \(k\) 元环。
\(n,m\leq 300,3\leq k\leq 10\)，无重边。
把 \(k=3\) 判掉，可以 \(O(m^2)\) 轻松解决。
把 \(k\) 元环拆成长度为 \(\dfrac{k}{2}-1\) 的链 \(+\) 长度 \(k-\dfrac{k}{2}-1\) 的链 \(+\) 连接两条链的两条边。（长度指边的个数）
问题：两条链需要无交。
解决方案：随机对每个点二元染色，钦定一条链为白色，另一条为黑色。
接下来只需要对每对点，找到以他们为链头权最大的长度 \(1\leq k'\leq 4\) 的链。
\(k'=1\)：链退化为，\(O(m)\)。
\(k'=2\)：枚举两条边判断是否有交，\(O(m^2)\)。
\(k'=3\)：枚举两条无交的边，判断能否在其之间再连一条边，\(O(m^2)\)。
\(k'=4\)：先进行 \(k'=2\) 的枚举，枚举时保留权值前三大的链，构造长度为 \(4\) 的链 \(=\) 边 \(+\) 长度为 \(2\) 的链 \(+\) 边，其中长为 \(2\) 的链的中点不能与其他四个点有交，所以保留前三大。\(O(m^2)\)。
预处理后即可 \(O(m^2)\) 简单合并黑白链。
复杂度支持做 \(O(m)\) 次随机化，误差可以接受。
卡随机化精度，请善用随机化技巧。
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <ctime>
// #define inf 0x3f3f3f3f3f3f3f3f
#define N 310
unsigned int sd = 114514;
bool rnd()
{
sd ^= sd << 13;
sd ^= sd >> 7;
sd ^= sd << 11;
return sd % 2;
}
int n, m, K;
int x_[N << 1], y_[N << 1], z_[N << 1];
int mp[2][N][N];
int ans;
bool col[N];
int f[2][N][N];
inline void ckmax(int &x, int y) { x = x > y ? x : y; }
inline void Set(bool c, int x, int y, int z)
{
ckmax(f[c][x][y], z);
ckmax(f[c][y][x], z);
}
bool check(bool c, int i)
{
return col[x_[i]] == c && col[y_[i]] == c;
}
int common(int i, int j)
{
if (x_[i] == x_[j] || x_[i] == y_[j])
return x_[i];
if (y_[i] == x_[j] || y_[i] == y_[j])
return y_[i];
return 0;
}
inline void solve1(bool c)
{
for (int i = 1; i <= m; i++)
if (check(c, i))
Set(c, x_[i], y_[i], z_[i]);
}
inline void solve2(bool c)
{
for (int i = 1; i <= m; i++)
if (check(c, i))
for (int j = i + 1, t; j <= m; j++)
if (check(c, j) && (t = common(i, j)))
Set(c, x_[i] ^ y_[i] ^ t, x_[j] ^ y_[j] ^ t, z_[i] + z_[j]);
}
inline void Link3(bool c, int i, int j)
{
if (mp[c][x_[i]][x_[j]])
Set(c, y_[i], y_[j], z_[i] + z_[j] + mp[c][x_[i]][x_[j]]);
if (mp[c][x_[i]][y_[j]])
Set(c, y_[i], x_[j], z_[i] + z_[j] + mp[c][x_[i]][y_[j]]);
if (mp[c][y_[i]][x_[j]])
Set(c, x_[i], y_[j], z_[i] + z_[j] + mp[c][y_[i]][x_[j]]);
if (mp[c][y_[i]][y_[j]])
Set(c, x_[i], x_[j], z_[i] + z_[j] + mp[c][y_[i]][y_[j]]);
}
inline void solve3(bool c)
{
for (int i = 1; i <= m; i++)
if (check(c, i))
for (int j = i + 1; j <= m; j++)
if (check(c, j) && !common(i, j))
Link3(c, i, j);
}
struct node
{
int mx1, mid1, mx2, mid2, mx3, mid3;
node()
{
mx1 = mx2 = mx3 = 0;
mid1 = mid2 = mid3 = 0;
}
bool empty() { return !mx1; }
void merge(int mx, int mid)
{
if (mx >= mx1)
{
mx3 = mx2, mx2 = mx1, mx1 = mx;
mid3 = mid2, mid2 = mid1, mid1 = mid;
}
else if (mx >= mx2)
{
mx3 = mx2, mx2 = mx;
mid3 = mid2, mid2 = mid;
}
else if (mx >= mx3)
{
mx3 = mx;
mid3 = mid;
}
}
} g[2][N][N];
node tmp;
inline void Link4(bool c, int i, int j)
{
if (!g[c][x_[i]][x_[j]].empty())
{
tmp = g[c][x_[i]][x_[j]];
if (tmp.mx1 && tmp.mid1 != y_[i] && tmp.mid1 != y_[j])
Set(c, y_[i], y_[j], z_[i] + tmp.mx1 + z_[j]);
if (tmp.mx2 && tmp.mid2 != y_[i] && tmp.mid2 != y_[j])
Set(c, y_[i], y_[j], z_[i] + tmp.mx2 + z_[j]);
if (tmp.mx3 && tmp.mid3 != y_[i] && tmp.mid3 != y_[j])
Set(c, y_[i], y_[j], z_[i] + tmp.mx3 + z_[j]);
}
if (!g[c][x_[i]][y_[j]].empty())
{
tmp = g[c][x_[i]][y_[j]];
if (tmp.mx1 && tmp.mid1 != y_[i] && tmp.mid1 != x_[j])
Set(c, y_[i], x_[j], z_[i] + tmp.mx1 + z_[j]);
if (tmp.mx2 && tmp.mid2 != y_[i] && tmp.mid2 != x_[j])
Set(c, y_[i], x_[j], z_[i] + tmp.mx2 + z_[j]);
if (tmp.mx3 && tmp.mid3 != y_[i] && tmp.mid3 != x_[j])
Set(c, y_[i], x_[j], z_[i] + tmp.mx3 + z_[j]);
}
if (!g[c][y_[i]][x_[j]].empty())
{
tmp = g[c][y_[i]][x_[j]];
if (tmp.mx1 && tmp.mid1 != x_[i] && tmp.mid1 != y_[j])
Set(c, x_[i], y_[j], z_[i] + tmp.mx1 + z_[j]);
if (tmp.mx2 && tmp.mid2 != x_[i] && tmp.mid2 != y_[j])
Set(c, x_[i], y_[j], z_[i] + tmp.mx2 + z_[j]);
if (tmp.mx3 && tmp.mid3 != x_[i] && tmp.mid3 != y_[j])
Set(c, x_[i], y_[j], z_[i] + tmp.mx3 + z_[j]);
}
if (!g[c][y_[i]][y_[j]].empty())
{
tmp = g[c][y_[i]][y_[j]];
if (tmp.mx1 && tmp.mid1 != x_[i] && tmp.mid1 != x_[j])
Set(c, x_[i], x_[j], z_[i] + tmp.mx1 + z_[j]);
if (tmp.mx2 && tmp.mid2 != x_[i] && tmp.mid2 != x_[j])
Set(c, x_[i], x_[j], z_[i] + tmp.mx2 + z_[j]);
if (tmp.mx3 && tmp.mid3 != x_[i] && tmp.mid3 != x_[j])
Set(c, x_[i], x_[j], z_[i] + tmp.mx3 + z_[j]);
}
}
inline void solve4(bool c)
{
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
g[c][i][j] = g[0][0][0];
for (int i = 1; i <= m; i++)
if (check(c, i))
for (int j = i + 1, t; j <= m; j++)
if (check(c, j) && (t = common(i, j)))
{
g[c][x_[i] ^ y_[i] ^ t][x_[j] ^ y_[j] ^ t].merge(z_[i] + z_[j], t);
g[c][x_[j] ^ y_[j] ^ t][x_[i] ^ y_[i] ^ t].merge(z_[i] + z_[j], t);
}
for (int i = 1; i <= m; i++)
if (check(c, i))
for (int j = i + 1, t; j <= m; j++)
if (check(c, j) && !common(i, j))
Link4(c, i, j);
}
inline void sve(bool c, int p)
{
if (p == 1)
solve1(c);
else if (p == 2)
solve2(c);
else if (p == 3)
solve3(c);
else if (p == 4)
solve4(c);
}
inline void Link0(int i, int j)
{
if (f[0][x_[i]][x_[j]] && f[1][y_[i]][y_[j]])
ckmax(ans, f[0][x_[i]][x_[j]] + f[1][y_[i]][y_[j]] + z_[i] + z_[j]);
}
inline void solve(int op)
{
for (int i = 1; i <= n; i++)
col[i] = rnd();
memset(f, 0, sizeof(f));
memset(mp, 0, sizeof(mp));
if (K == 3)
{
for (int i = 1; i <= m; i++)
mp[0][x_[i]][y_[i]] = mp[0][y_[i]][x_[i]] = z_[i];
for (int i = 1; i <= m; i++)
for (int j = i + 1, t; j <= m; j++)
if ((t = common(i, j)))
if (mp[0][x_[i] ^ y_[i] ^ t][x_[j] ^ y_[j] ^ t])
ckmax(ans, z_[i] + z_[j] + mp[0][x_[i] ^ y_[i] ^ t][x_[j] ^ y_[j] ^ t]);
return;
}
for (int i = 1; i <= m; i++)
if (col[x_[i]] == col[y_[i]])
mp[col[i]][x_[i]][y_[i]] = mp[col[i]][y_[i]][x_[i]] = z_[i];
int R = K / 2 - 1;
int L = K - K / 2 - 1;
if (op)//fuck
std::swap(L, R);
sve(0, L);
sve(1, R);
for (int i = 1; i <= m + m; i++)
if (col[x_[i]] == 0 && col[y_[i]] == 1)
for (int j = 1; j <= m + m; j++)
if (col[x_[j]] == 0 && col[y_[j]] == 1)
Link0(i, j);
}
int read()
{
int x = 0;
char c = getchar();
while (c < '0' || '9' < c)
c = getchar();
while ('0' <= c && c <= '9')
{
x = (x << 3) + (x << 1) + (c ^ 48);
c = getchar();
}
return x;
}
signed main()
{
n = read(), m = read(), K = read();
for (int i = 1; i <= m; i++)
x_[i] = read(), y_[i] = read(), z_[i] = read();
for (int i = 1; i <= m; i++)
x_[i + m] = y_[i], y_[i + m] = x_[i], z_[i + m] = z_[i];
int op = 0;
while (1.0 * clock() / CLOCKS_PER_SEC <= 2.97)
solve(op ^= 1);
if (!ans)
printf("impossible\n");
else
printf("%d\n", ans);
return 0;
}