放牧代码和思想
专注自然语言处理、机器学习算法
    博主不用扣扣,公事请博客留言,私事请微博私信。开源项目一律GitHub见,发错地方恕不回复,谢谢。

POJ 2723 Get Luffy Out 题解《挑战程序设计竞赛》

目录

挑战程序设计竞赛第二版.jpg

POJ 2723 Get Luffy Out 

鸳鸯锁:你的基友路飞被关进了一座M层的监狱,每层的门上由两把锁锁住,打开任意一把即可入内。这些锁的钥匙一共有2N种,两两互斥,当使用了一把钥匙后,另一把与其互斥的钥匙就会消失,造成鸳鸯锁永远只能解开一把。给定锁的配对关系和门上锁的编号,请计算最高能到达的层数。

4.3成为图论大师之路 

2-SAT

很哲学的题目。

任意一道门都是一个子句,两把锁A和B是OR的关系,写成蕴含式:

A OR B = 1   <=>   !A->B AND !B->A

能通过m道门,则将m个子句and起来即可,典型的2-SAT问题。

给定m,可以用上述思路验证,不过题目求的是最大的m。考虑到如果第x层通不过,则x后面的门也通不过,有种单调性。所以可以用二分法去快速搜索最大的m。

#include <iostream>
#include <cstring>
#include <vector>

using namespace std;
#define MAX_N 1 << 10
#define MAX_M 1 << 11
#define MAX_V 2 * MAX_N

int V;                      // 顶点数
vector<int> G[MAX_V];       // 图的邻接表表示
vector<int> rG[MAX_V];      // 反向图
vector<int> vs;             // 后序遍历顺序的顶点列表
bool used[MAX_V];           // 访问标记
int cmp[MAX_V];             // 所属强连通分量的拓补序

void add_edge(const int &from, const int &to)
{
    G[from].push_back(to);
    rG[to].push_back(from);
}

void dfs(const int &v)
{
    used[v] = true;
    for (int i = 0; i < G[v].size(); ++i)
    {
        if (!used[G[v][i]])
            dfs(G[v][i]);
    }
    vs.push_back(v);
}

void rdfs(const int &v, const int &k)
{
    used[v] = true;
    cmp[v] = k;
    for (int i = 0; i < rG[v].size(); ++i)
    {
        if (!used[rG[v][i]])
            rdfs(rG[v][i], k);
    }
}

int scc()
{
    memset(used, 0, sizeof(used));
    vs.clear();
    for (int v = 0; v < V; ++v)
    {
        if (!used[v])
            dfs(v);
    }
    memset(used, 0, sizeof(used));
    int k = 0;
    for (int i = vs.size() - 1; i >= 0; --i)
    {
        if (!used[vs[i]])
            rdfs(vs[i], k++);
    }

    return k;
}

int M, N;
int keys[MAX_V];        // keys[i] := 与i互斥的那把钥匙
int doors[MAX_M][2];    // 每个门上的两把锁

bool is_able(int m)
{
    V = 2 * N;
    for (int i = 0; i < V; i++)
    {
        G[i].clear();
        rG[i].clear();
    }
    for (int i = 0; i < m; i++)
    {
        // A OR B = 1   <=>      !A->B AND !B->A
        add_edge(keys[doors[i][0]], doors[i][1]);
        add_edge(keys[doors[i][1]], doors[i][0]);
    }
    scc();
    for (int i = 0; i < V; i++)
    {
        if (cmp[i] == cmp[keys[i]])
        {
            return false;
        }
    }

    return true;
}

int solve()
{
    int low = 0, high = M + 1;
    while (high - low > 1)
    {
        int mid = (high + low) / 2;
        if (is_able(mid))
        {
            low = mid;
        }
        else
        {
            high = mid;
        }
    }

    return low;
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    while (~scanf("%d%d", &N, &M) && M && N)
    {
        for (int i = 0; i < N; i++)
        {
            int A, B;
            scanf("%d%d", &A, &B);
            keys[A] = B;
            keys[B] = A;
        }
        for (int i = 0; i < M; i++)
        {
            scanf("%d%d", doors[i], doors[i] + 1);
        }

        printf("%d\n", solve());
    }
#ifndef ONLINE_JUDGE
    fclose(stdin);
#endif
    return 0;
}
16452621 hankcs 2723 Accepted 452K 47MS C++ 2521B 2017-01-06 11:52:41

做完后满脑子都是FA♂乐器

哲学.jpg

知识共享许可协议 知识共享署名-非商业性使用-相同方式共享码农场 » POJ 2723 Get Luffy Out 题解《挑战程序设计竞赛》

分享到:更多 ()

评论 欢迎留言

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

我的开源项目

HanLP自然语言处理包基于DoubleArrayTrie的Aho Corasick自动机