$\texttt{Subtask 1}$:

暴力枚举即可。

$\texttt{Subtask 2}$:

回溯加适当剪枝有可能通过。

$\texttt{Subtask 3}$:

方法 $1$：将问题建模为最小费用最大流问题予以解决。如果存在满足题意要求的座位安排方案，则每位大使都必须和另外一位大使唯一配对。将大使对应的顶点拆分为前点后后点，在前点和后点间建立一条容量为 $1$ 费用为 $h_{i,j}$ 的有向弧，然后建立超级源点和超级汇点，从超级源点向每个前点建立一条容量为 $1$ 费用为 $0$ 的有向弧，从每个后点向超级汇点建立一条容量为 $1$ 费用为 $0$ 的有向弧，在此容量网络上运行最小费用最大流算法，如果能够满流，则符合题意要求的餐桌安排方案存在，输出最小费用即可。

方法 $2$：将问题建模为最大权完毕匹配问题予以解决。分析题目可知，坐在圆桌上相邻的两位大使必须要互相认识，由于认识是相互的，等价于任意一个人都与其他某个人进行唯一匹配，在达到这样的匹配后，将大使视为图的顶点，则这样给定的 $n$ 个人构成了若干个有向圈，每个有向圈对应一个餐桌的安排（可能有多种安排方案）。因此，题目本质就是最小权完备匹配，将厌恶度值取反然后使用最大权完备匹配算法——$\text{Kuhn-Munkres}$ 算法即可。如果不加优化实现，时间复杂度为 $O(n^4)$，优化后的时间复杂度为 $O(n^3)$。

$\texttt{Subtask 4}$:

方法 $1$：优化的最小费用最大流算法实现。

方法 $2$：优化的最大权完毕匹配实现，时间复杂度 $O(n^3)$。

参考代码：

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 710;
const long long INF = 0x7f7f7f7f7f7f7f7f;

int linky[MAXN], cx[MAXN], cy[MAXN], visited[MAXN];
long long weight[MAXN][MAXN], lx[MAXN], ly[MAXN], slack[MAXN];
int n, m;

bool dfs(int x)
{
    cx[x] = true;
    for (int y = 0; y < n; y++) {
        if (cy[y]) continue;
        long long delta = lx[x] + ly[y] - weight[x][y];
        if (delta == 0) {
            cy[y] = true;
            if (linky[y] == -1 || dfs(linky[y])) {
                linky[y] = x;
                return true;
            }
        }
        else slack[y] = min(slack[y], delta);
    }
    return false;
}

void kuhnMunkres()
{
    for (int i = 0; i < n; i++)
    {
        linky[i] = -1, lx[i] = 0, ly[i] = 0;
        for (int j = 0; j < n; j++)
            lx[i] = max(lx[i], weight[i][j]);
    }
    for (int x = 0; x < n; x++)
        while (true) {
            memset(cx, 0, sizeof(cx));
            memset(cy, 0, sizeof(cy));
            for (int i = 0; i < n; i++) slack[i] = INF;
            if (dfs(x)) break;
            long long delta = INF;
            for (int i = 0; i < n; i++)
                if (!cy[i])
                    delta = min(delta, slack[i]);
            for (int i = 0; i < n; i++) {
                if (cx[i]) lx[i] -= delta;
                if (cy[i]) ly[i] += delta;
            }
        }
}

int main(int argc, char *argv[])
{
    cin.tie(0), cout.tie(0), ios::sync_with_stdio(false);


    cin >> n >> m;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            weight[i][j] = -INF;
    for (int i = 0, u, v, w; i < m; i++)
    {
        cin >> u >> v >> w;
        u--, v--;
        weight[u][v] = -w;
    }
    kuhnMunkres();
    long long r = 0;
    for (int y = 0; y < n; y++)
    {
        if (weight[linky[y]][y] != -INF)
            r -= weight[linky[y]][y];
        else
        {
            r = -1;
            break;
        }
    }
    if (r < 0) cout << "Impossible!\n";
    else 
    {
        cout << r << '\n';
        for (int i = 0; i < n; i++)
            if (!visited[i])
            {
                visited[i] = 1;
                int u = i, v = linky[i];
                vector<int> stk;
                stk.push_back(u + 1);
                while (v != u)
                {
                    visited[v] = 1;
                    stk.insert(stk.begin(), v + 1);
                    v = linky[v];
                }
                for (int j = 0; j < stk.size(); j++)
                {
                    if (j) cout << ' ';
                    cout << stk[j];
                }
                cout << '\n';
            }
    }

    return 0;
}