首页 > 其他分享 >P4298 [CTSC2008] 祭祀 题解

P4298 [CTSC2008] 祭祀 题解

时间:2024-04-15 21:33:49浏览次数:31  
标签:匹配 覆盖 标记 int 题解 P4298 CTSC2008 反链 match

P4298 [CTSC2008] 祭祀 题解

给定 DAG,求最长反链长度,最长反链方案,有多少个点可以成为反链上的点。

Case 1

熟知 Dilworth 定理:偏序集的最长反链的长度等于最小链划分。

因为偏序集有传递性,所以我们也需要对 DAG 做一遍传递闭包。

这样可以套用 Dilworth 定理,最小链划分等于点数减去最大匹配数,所以使用二分图最大匹配算法就可以在 \(O(n^3)\) 的时间复杂度内解决这个问题,当然可以用更优的网络流算法,不过没必要。

Case 2

找出最小点覆盖,所有入点和出点都不是最小点覆盖元素的就是一个反链元素。

Step 1

找出最小点覆盖。

考虑如下算法:

从所有非匹配点开始,找到所有一条由非匹配边开始的交错轨,标记交错轨(注意,肯定没法找到增广轨)上的节点。

断言:所有入点未标记和出点被标记的点的并就是最小点覆盖。

证明:

首先它的大小是最小点覆盖的大小,因为一条匹配边要么左右部都未标记要么都被标记,所以大小就是最大匹配的大小,根据 Konig 定理,最大匹配大小等于最小点覆盖大小。

接着证明它覆盖了所有点。

  1. 对于匹配边,左右部标记状态相同,所以一定它被覆盖
  2. 对于非匹配边,如果它左部未标记或右部被标记显然它被覆盖了,否则:
    1. 左部被标记,则右部一定被标记,因为这是一定是一条交错轨的一部分。
    2. 右部未被标记,则左部一定未被标记,否则右部就被访问了。

综上,此方案为一种最小点覆盖。

Step 2

根据 Dilworth 定理的证明易知。

Case 3

比上两问思维难度低,我们只需要钦定每个点是反链的元素,然后求出剩余和这个点没有偏序关系的点的最大反链,如果加入此点后是原偏序集最大反链,那么这个点就可以成为最大反链的元素。

参考代码

时间复杂度:\(O(n^{1.5}m + \dfrac{n^3}{w})\sim O( n^2m + n^3)\),瓶颈在二分图最大匹配上。

// Problem: P4298 [CTSC2008] 祭祀
// Contest: Luogu
// Author: Moyou
// Copyright (c) 2024 Moyou All rights reserved.
// Date: 2024-04-15 20:34:52

#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
// #define int long long
using namespace std;
const int N = 100 + 10, M = 1e3 + 10;

int n, match[N], m, d[N][N], mac;
bool st[N], del[N], mm[N];
vector<int> g[N];
int find(int x) {
    if(del[x]) return 0;
    for(auto v : g[x]) {
        if(st[v] || del[v]) continue;
        st[v] = 1;
        if(!match[v] || find(match[v]))
            return mm[x] = 1, match[v] = x;
    }
    return 0;
}
bool ok[N * 2];
void dfs(int x) {
    if(ok[x]) return ; ok[x] = 1;
    for(auto v : g[x]) {
        if(ok[v + n]) continue;
        ok[v + n] = 1;
        if(match[v])
            dfs(match[v]);
    }
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for(int i = 1, a, b; i <= m; i ++) {
        cin >> a >> b;
        d[a][b] = 1;
    }
    for(int k = 1; k <= n; k ++) for(int i = 1; i <= n; i ++) for(int j = 1; j <= n; j ++) d[i][j] |= d[i][k] & d[k][j];
    for(int i = 1; i <= n; i ++) for(int j = 1; j <= n; j ++) if(d[i][j]) g[i].push_back(j);
    mac = n;
    for(int i = 1; i <= n; i ++) {
        if(find(i)) mac --;
        memset(st, 0, sizeof st);
    }
    cout << mac << '\n';
    for(int i = 1; i <= n; i ++)
        if(!mm[i]) dfs(i);
    for(int i = 1; i <= n; i ++)
        cout << (ok[i] && !ok[i + n]); cout << '\n';
    for(int i = 1, maa; i <= n; i ++) {
        memset(del, 0, sizeof del), memset(match, 0, sizeof match);
        maa = n;
        for(int j = 1; j <= n; j ++) if(d[j][i] || d[i][j] || j == i) del[j] = 1, maa --;
        for(int j = 1; j <= n; j ++) {
            if(del[j]) continue;
            if(find(j)) maa --;
            memset(st, 0, sizeof st);
        } 
        cout << (maa + 1 == mac);
    }

    return 0;
}

标签:匹配,覆盖,标记,int,题解,P4298,CTSC2008,反链,match
From: https://www.cnblogs.com/MoyouSayuki/p/18136943

相关文章

  • [题解][2021-2022年度国际大学生程序设计竞赛第10届陕西省程序设计竞赛] Hash
    题目描述给定字符串T,要求求字符串S,满足以下条件:S是T的前缀S和T运行某段代码的哈希值相同(代码见下)T只包含小写字母S和T的长度差不超过50哈希代码://LanguageC++14longlongmod=5999993;longlonggethas(strings){longlongret=0;for(charc:s)ret=......
  • PGSQL 问题解决
    1服务无法启动 这里更改安装目录bin下面例如E:\WorkingSoftware\PostgreSql\16\bin更改权限,下面都改下 2  安装时提示database出错,就初始化下执行以下命令E:\WorkingSoftware\PostgreSql\16\bin\pg_ctl.exe-DE:\WorkingSoftware\PostgreSql\16\dat......
  • 2024小学组AHOI赛后题解
    观看建议调成浅色模式(右下角图标)写前扯一下这次省赛可谓是人才辈出啊。结束前一个半小时就交卷,可见这次考试的难度。后我问他们是不是很有信心AKXX:做了前两题,后两题崩溃了。。。好吧,其实第三题没那么难,不过AK的真没有,听说没有一个人做对。接下来带大家看看这几题。(记得,看......
  • CF1253F Cheap Robot 题解
    首先建立一个超级点\(S\),对于每一个可以充电的点\(u\)都建立一条从\(S\tou\)的边权为\(0\)的有向边。从这个超级点\(S\)开始跑一遍最短路算法,就可以得到每一个点\(u\)至少需要花费多少的电量才可以走到一个充电点。令\(D_i\)表示\(i\)号点最少花费多少可以到一个......
  • LlamaIndex 常见问题解答(FAQ)
     提示:如果您尚未完成,请安装LlamaIndex并完成起步教程。遇到不熟悉的术语时,请参考高层次概念部分。在这个章节中,我们将从您为起步示例编写的代码开始,展示您可能希望针对不同应用场景对其进行的常见定制方法:python fromllama_index.coreimportVectorStoreIndex,Simp......
  • P4383 林克卡特树 题解
    题意:给定带边权的树,要切掉\(k\)条边,再任意连上\(k\)条边权为\(0\)的边。问最优策略下得到的树的边权最大值。\(n,k\le3\times10^5\)。参考【问题转化】切掉\(k\)条边后会变成\(k+1\)个连通块,之后的连边一定会把这\(k+1\)个连通块的直径连起来。所以相当于问把......
  • [题解](A-G)Atcoder Educational DP Contest(更新中)
    AtcoderEducationalDPContest\(\textbf{A.Frog1}\)对于一块石头\(i(3\lei\leN)\),\(i-1\)和\(i-2\)均能到达。用\(f[i]\)表示跳到第\(i\)个石头用的最小体力消耗:\[f[i]=min(abs(h[i]-h[i-1])+f[i-1],abs(h[i]-h[i-2])+f[i-2])\qquadi\ge3\]时间复杂度\(O(n)\)。......
  • 华中农业大学第十三届程序设计竞赛 题解
    A-scx的散文诗句Solution正负分开来分别处理,按照绝对值从大到小排序,两两匹配注意:当没有\(0\)且正数和负数都为奇数,即最后剩下一个正数一个负数时,必须匹配Code#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;voidsolve(){intn;cin>......
  • [题解]P1629 邮递员送信
    好久不写图论题了,Dijkstra都花了好长时间捡起来……之前也没有接触过反图的概念。这个题算是我重拾图论知识以来的第一题了。__φ(..)P1629邮递员送信Dijkstra是单源最短路的算法。但这个题除了要求节点\(1\)到其他节点的距离,还要知道其他节点回到节点\(1\)的距离。如果我们每个......
  • [POI2012] Rendezvous 题解
    众所周知,\(lyh\)是一名压行大师,也是一名\(juruo\),所以他将他繁琐的方法用\(102\)行表现了出来……明显原题为基环内向树森林。首先用并查集计算连通块,不在一个连通块里的答案就是\(-1\-1\)。发现实际上答案就是以环为根节点,求\(lca\)的结果,求完后可以分为两种情况:根......