题解 P1525 【关押罪犯】

· · 题解

题目大意

有n个罪犯，要将它们分成两个集合。给出m对关系(x,y,val)，表示若将x,y分到同一集合中，会产生val的怨气值；若未给出关系，则说明(x,y)分到同一集合怨气值为0。询问最小化最大怨气值。n<=20000,m<=100000

思考方向1

首先想到将最优性问题转化为判断性问题，简化求解。

即：枚举最大怨气值maxa，令val小于等于maxa的边（包括边权为0的边）才能存在，判定是否可行。问题转化成如何判定1个图能否被划分成两个完全图。

如果正向判断，会因为各边错综复杂，限制不明确而难以求解。

尝试反向判断，考虑存在合法方案时，补图的相关限制。由于“完全图”的限制，这些实际不存在的边的顶点必须分属两个集合，因此补图为二分图为必要条件。尝试证明充分性，若补图为二分图，则不存在 同一集合的两点间没有连边 的情况，则两集合一定均为完全图。故补图为二分图为充要条件，证毕。

问题转化成如何判定图是否为二分图。

实现方式1

DFS染色判定二分图。单次判定时间复杂度O（N+M）

由于答案具有单调性，二分最大怨气值优化。

综上，二分最大怨气值 + 二分图染色 即可。时间复杂度O((N+M)logM)

实现方式2

二分图判定其实是矛盾关系的判定，考虑并查集。

传统的并查集只能维护点的连通性问题。当点之间存在多种关系，且关系具有传递性时，就要使用 带权并查集 或者 扩展域并查集。

时间复杂度O(MlogM)

关于 带权并查集 与 扩展域并查集

带权并查集在并查集的基础上，通过边权维护各点间的关系。点与根的关系需要通过点与父亲、父亲与根的关系推算；两点间的实际关系需要通过两点与根的关系推算；合并两个集合时需要推算出两根的关系。难点主要在于如何将关系及其传递性用数值和相应的算式体现，以实现查询与合并。

扩展域并查集则另辟蹊径，将1个点拆分成若干虚点，通过合并虚点维护各点间的关系。相比起带权并查集，优点在于仅用到传统的并查集；缺点在于 空间复杂度 为 点数*状态数，而且需要全面考虑体现在扩展域上的所有等价关系。 _插一句题外话：这种“拆点”思想是非常美妙且常用的思想，广泛应用于各种算法/习题。

实际上，这两种应用最经典的体现应该是食物链

回归本题

下文用“敌对”“友好”代替点对在二分图中的关系。

1.带权并查集 解法

设边权1表示敌对，边权0表示友好。关系的传递性利用%的性质体现。

已知x与fa的关系,fa与根的关系，求x与根关系：Rel[x] = (Rel[x] + Rel[Fa[x]])%2;

x,y同属1集合，已知x,y与根的关系，求x与y的关系：rel(x,y) = (Rel[x] + Rel[y])%2

x,y不属1集合，已知x与y的关系，已知x与rootx，y与rooty的关系，求rootx与rooty的关系：Rel[rootx] = (Rel[x] + rel(x,y) + Rel[y])%2

主体代码如下:

int findA(int x)
{
    if(Fa[x] == x)  return x;
    int temp = findA(Fa[x]);
    Rel[x] = (Rel[x] + Rel[Fa[x]]) % 2;
    return Fa[x] = temp;
}
void Merge(int x,int y,int rootx,int rooty)
{
    int rel = (Rel[x] + 1 + Rel[y]) % 2;
    Fa[rootx] = rooty;
    Rel[rootx] = rel;
}
void Calc()
{
    int ans = 0;
    for(int i = 1 ; i <= m ; i ++)
    {
        int x = Edge[i].x , y = Edge[i].y , w = Edge[i].w;
        int rootx = findA(x) , rooty = findA(y);
        if(rootx != rooty)  Merge(x,y,rootx,rooty);
        else    
        {
            int rel = (Rel[x] + Rel[y]) % 2;
            if(rel == 0)    
            {
                ans = w;
                break;
            }
        }
    }
    printf("%d\n",ans);
}

2.扩展域并查集 解法

x的敌对域/友好域：x , x + n

询问x,y关系：询问x,y的敌对域x,y是否为同1集合，若是则x,y为同类，否则反之。即if(rootx == rooty) x,y为同类。

维护x,y敌对关系：合并x的敌对域与y的友好域、x的友好域与y的敌对域，即Merge(x,y+n),Merge(x+n,y);

主体代码如下：

int findA(int x)
{
    if(Fa[x] == x)  return x;
    return Fa[x] = findA(Fa[x]);
}
void Merge(int x,int y)
{
    int rootx = findA(x) , rooty = findA(y);
    Fa[rootx] = rooty;
}
void Calc()
{
    int ans = 0;
    for(int i = 1 ; i <= m ; i ++)
    {
        int x = Edge[i].x , y = Edge[i].y , w = Edge[i].w;
        if(findA(x) == findA(y))//两者的敌对域属于同1集合，则两者为同类   
        {
            ans = w;
            break;
        }   
        else    
        {
           //将x的敌对域与y的友好域合并，将x的友好域与y的敌对域合并。 
            Merge(x,y + n);
            Merge(x + n ,y);
        }
    }
    printf("%d\n",ans);
}

思考方向二

最小化最大边权，则考虑贪心。 为了最大边权尽可能小，尽可能删除边权较大的边，因此按照边权从大到小排序，依次取出试图将其顶点染成不同的颜色。最终做法与上文相同，不过不失为另一种思考的好方向。