专栏首页ACM小冰成长之路POJ-3866-Exclusive Access 2

POJ-3866-Exclusive Access 2

ACM模版

描述

题解

这绝对是我做过最长的题,也是最难理解的题,翻译成中文都很难理解。

简单的说,就是安排任务使用两个资源的顺序,使最坏情况下,执行任务的等待时间最短。

sdfzyhx’s blog 说可以将资源看成点,任务看成无向边,任务就是把无向边定向,使图中不存在环并且最长链最短。

然后就是根据一个 DilworthDilworth 定理搞搞,把点分成 mm 部分,使每一部分内部没有边,mm 的最小值就是最长链的最小值,然后状压 DPDP 即可求解着色问题。

说的我懵懵的,这个题真心恶心~~~

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>

using namespace std;

const int MAXN = 20;
const int MAXM = 111;

map<char, int> mci;
map<int, char> mic;

int n, m;
bool ok[1 << MAXN];
bool g[MAXN][MAXN];
char s1[MAXN];
char s2[MAXN];
int q1[MAXM];
int q2[MAXM];
int num[MAXN];
int pre[1 << MAXN];
int dp[1 << MAXN];

int main()
{
    scanf("%d", &m);

    int u, v;
    for (int i = 1; i <= m; i++)
    {
        scanf("%s%s", s1, s2);

        if (!mci.count(s1[0]))
        {
            mic[n] = s1[0];
            mci[s1[0]] = n++;
        }
        if (!mci.count(s2[0]))
        {
            mic[n] = s2[0];
            mci[s2[0]] = n++;
        }
        u = mci[s1[0]];
        v = mci[s2[0]];
        q1[i] = u;
        q2[i] = v;
        g[u][v] = g[v][u] = 1;
    }

    ok[0] = 1;
    for (int i = 1; i < (1 << n); i++)
    {
        ok[i] = 1;
        for (int j = 0; j < n; j++)
        {
            if (i & (1 << j))
            {
                if (!ok[i ^ (1 << j)])
                {
                    ok[i] = 0;
                    break;
                }

                for (int k = 0; k < n; k++)
                {
                    if (j != k && (i & (1 << k)) && g[j][k])
                    {
                        ok[i] = 0;
                        break;
                    }
                }

                break;
            }
        }
    }

    memset(dp, 0x3f, sizeof(dp));

    dp[0] = 0;
    for (int i = 1; i < (1 << n); i++)
    {
        for (int j = i; j; j = i & (j - 1))
        {
            if (ok[j] && dp[i ^ j] + 1 < dp[i])
            {
                dp[i] = dp[i ^ j] + 1;
                pre[i] = j;
            }
        }
    }

    printf("%d\n", dp[(1 << n) - 1] - 2);

    for (int i = (1 << n) - 1, clo = 1; i; i ^= pre[i], clo++)
    {
        for (int j = 0; j < n; j++)
        {
            if ((1 << j) & pre[i])
            {
                num[j] = clo;
            }
        }
    }

    for (int i = 1; i <= m; i++)
    {
        if (num[q1[i]] < num[q2[i]])
        {
            printf("%c %c\n", mic[q1[i]], mic[q2[i]]);
        }
        else
        {
            printf("%c %c\n", mic[q2[i]], mic[q1[i]]);
        }
    }

    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • HDU-5985-Lucky Coins

    ACM模版 描述 ? 题解 image.png 代码 #include <iostream> #include <cstdio> #include <cstri...

    f_zyj
  • HDU-5534-Partial Tree

    ACM模版 描述 ? 题解 image.png 代码 #include <iostream> #include <cstdio> #include <algor...

    f_zyj
  • 51Nod-1874-字符串排序

    ACM模版 描述 ? 题解 很简单的一个逆序数问题,不过因为一个坑点,WAWA 了好几发,一开始把 nn 和 mm 看反了…… 代码 #include <ios...

    f_zyj
  • 1009 产生数 2002年NOIP全国联赛普及组

    009 产生数 2002年NOIP全国联赛普及组 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题目描述 De...

    attack
  • LeetCode 135 Candy

    ShenduCC
  • POJ-1088 滑雪 (记忆化搜索,dp)

    滑雪 Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 86318 ...

    ShenduCC
  • HDU 3078 Network

    Problem Description The ALPC company is now working on his own network system,...

    attack
  • Lake Counting (POJ No.2386)

    题意:有一个M*N的圈子,雨后有积水,然后八个方位相联通的被认为是连接在一起的。请求出圈子里共有多少个水洼。

    用户7727433
  • 洛谷P1734 最大约数和

    题目描述 选取和不超过S的若干个不同的正整数,使得所有数的约数(不含它本身)之和最大。 输入输出格式 输入格式: 输入一个正整数S。 输出格式: 输出最大的约...

    attack
  • 数独终盘生成的几种方法

    为了完成矩阵的转换,我们需要有可用的数独终盘矩阵作为种子矩阵才行。可以采用如下做法完成:

    孟君

扫码关注云+社区

领取腾讯云代金券