1 条题解

  • 0
    @ 2021-6-13 19:40:22

    Subtask 1\texttt{Subtask 1}:

    暴力枚举即可。

    Subtask 2\texttt{Subtask 2}:

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

    Subtask 3\texttt{Subtask 3}:

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

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

    Subtask 4\texttt{Subtask 4}:

    方法 11:优化的最小费用最大流算法实现。

    方法 22:优化的最大权完毕匹配实现,时间复杂度 O(n3)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;
    }
    
    • 1

    信息

    ID
    146
    时间
    1000ms
    内存
    128MiB
    难度
    8
    标签
    递交数
    25
    已通过
    6
    上传者