Luogu P3231 [HNOI2013]消毒 — 二分图匹配

题目

题目链接: [https://www.luogu.org/problemnew/show/P3231]

先考虑一下,如果这张图是一个二维的情况?

对于每一个需要消毒的点的 $x,y$ 相互链接,然后直接跑最小点覆盖就对了

三维的情况?

三分图匹配?

不会,但是显然我们可以知道,如果我们设$ x $为三边中最小值则
$$ x \leq \sqrt[3]{5000} $$
也就约等于$$ x \leq 17$$

直接$ 2^{17} $ 枚举每一层选或者不选即可….

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
inline int Min(int a, int b) { return a < b ? a : b; }
const int N = 5e3 + 1e2;
const int INF = 0x4fffffff;
int T, u, v, w, op, res, ans;
int len[3], vis[30], match[30], vcnt, pos;
bool chose[30];
// edge start
struct edge {
    int to, next, val;
} e[N << 1];
int ehead[N], ecnt;
inline void add_edge(int now, int to, int val) {
    ecnt++;
    e[ecnt].to = to;
    e[ecnt].val = val;
    e[ecnt].next = ehead[now];
    ehead[now] = ecnt;
}
// edge end
inline void init() {
    memset(vis, 0, sizeof(vis));
    memset(ehead, 0, sizeof(ehead));
    ecnt = vcnt = 0;
    ans = INF;
}
inline void readin() {
    scanf("%d%d%d", &len[0], &len[1], &len[2]);
    if (len[0] <= len[1] && len[0] <= len[2])
        pos = 0;
    else if (len[1] <= len[2] && len[1] <= len[0])
        pos = 1;
    else
        pos = 2;
    for (int i = 1; i <= len[0]; i++) {
        for (int j = 1; j <= len[1]; j++) {
            for (int k = 1; k <= len[2]; k++) {
                scanf("%d", &op);
                if (!op)
                    continue;
                if (pos == 0)
                    add_edge(j, k, i);
                else if (pos == 1)
                    add_edge(k, i, j);
                else if (pos == 2)
                    add_edge(i, j, k);
            }
        }
    }
}
bool eft(int now) {
    for (int i = ehead[now]; i; i = e[i].next) {
        if (!chose[e[i].val] && vis[e[i].to] < vcnt) {
            vis[e[i].to] = vcnt;
            if (!match[e[i].to] || eft(match[e[i].to])) {
                match[e[i].to] = now;
                return true;
            }
        }
    }
    return false;
}
inline int get_ans(int now) {
    res = 0;
    memset(match, 0, sizeof(match));
    for (int i = 1; i <= len[(pos + 1) % 3]; i++) {
        vcnt++;
        if (eft(i))
            res++;
        if (res + now >= ans)//最优化剪枝
      return ans;
    }
    return res + now;
}
void dfs(int now, int sum) {
    if (now > len[pos]) {
        ans = Min(get_ans(sum), ans);
        return;
    }
    chose[now] = 1;
    dfs(now + 1, sum + 1);
    chose[now] = 0;
    dfs(now + 1, sum);
}
inline void work() {
    dfs(1, 0);
    printf("%d\n", ans);
}
int main() {
#ifndef ONLINE_JUDGE
    freopen("bzoj.3140.in", "r", stdin);
    freopen("bzoj.3140.out", "w", stdout);
#endif
    scanf("%d", &T);
    while (T--) {
        init();
        readin();
        work();
    }
}
]]>

Luopu P1525 关押罪犯 —— 初学二分图

二分图

二分图是什么?可以吃吗
可以吃而且很好吃 当然不可以吃,但是使用起来可是个好东西 对于一张无向图,如果他的所有的点可以分成两个点集,且每个点集内的点没有边相连,我们就称这张图为二分图 对于判定二分图,我们有一种非常简单的方法 —— 染色法

染色法


染色?染什么色?
实际上如果有精通小学奥数的同学应该知道,我们在解决一类问题的时候,就会用到染色法来分类,当然,今天的原理,和那个染色法有一点类似 根据二分图的定义每个点集内的点没有边相连,我们可以知道,和一个点相连的两条边一定不在同一个集合中,那么如何判断是不是在同一集合呢? 我们就可以吧同一类的染上一个颜色,然后遍历图,如果我们在遍历某个点的时候,发现下一个点已经遍历过了,且和当前点颜色一样,那么这一定不是二分图 代码如下:
inline bool bfs(int u){// u 起始点
    head=tail=0;// 队列初始化
    col[u]=1;// 初始化起点
    q[head]=u;// 加入对头
    while(head<=tail){// 标准不解释
        int top=q[head];// 去头部
        for(int i=ehead[top];i;i=e[i].next){// 标准遍历不解释
            int to=e[i].to;
            if(col[to]==0){// 如果没有被访问过
                col[to]=3-col[top];// 染色
                q[++tail]=to;// 加入队列
            }
            else {// 访问过
                if(col[to]==col[top]) return false;// 颜色相同当然不是二分图了
            }
        }
        head++;
    }
    return true;
}
但是有的时候,输入数据不保证为一张图,这个时候就要遍历点,如果当前点没有访问过,那么就从当前点起始染色

Luopu P1525 关押罪犯

二分查找二分图 题目链接: [https://www.luogu.org/problemnew/show/P1525]
第一眼看过去,这是什么?可和二分图有啥关系 然后看了看书,突然就明白了 我们可以二分事件的最大影响值,把每个罪犯看做一个点,如果影响值大于mid那么就链接,否则当不存在这条边 所以这道题目就是一个二分模板+染色判二分图

程序


#include <cstdio>
#include <cstring>
using namespace std;
int n,m;
int u,w,v;
int l,r,mid,max;
// edge start
struct edge{
    int to,next,val;
}e[210000];
int ehead[21000],ecnt;
inline void add(int now,int to,int val){
    ecnt++;
    e[ecnt].to=to;
    e[ecnt].val=val;
    e[ecnt].next=ehead[now];
    ehead[now]=ecnt;
}
// edge end
// edge 链表建图部分
// queue start
int q[110000],head,tail;
int col[110000];
inline bool bfs(int u){
    head=tail=0;
    col[u]=1;
    q[head]=u;
    while(head<=tail){
        int top=q[head];
        for(int i=ehead[top];i;i=e[i].next){
            int to=e[i].to;
            if(e[i].val>=mid){// 大于等于mid时建边
                if(col[to]==0){
                    col[to]=3-col[top];
                    q[++tail]=to;
                }
                else {
                    if(col[to]==col[top]) return false;
                }
            }
        }
        head++;
    }
    return true;
}
// queue end
// queue 染色法判图
inline bool rs(){
    for(int i=1;i<=n;i++){
        if(col[i]==0)
            if(!bfs(i)) return false;
    }
    return true;
}
// rs 遍历点
inline void init(){
    memset(col,0,sizeof(col));
}
// init 预处理
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&u,&v,&w);
        max=max>w?max:w;// 保留最大用于二分上限
        add(u,v,w);
        add(v,u,w);
    }
    l=0,r=max+1;// 标准二分
    while(l+1<r){
        init();
        mid=(l+r)>>1;
        if(rs()) r=mid;// 如果可以达成[二分图成立] 则缩小范围
        else l=mid;// 不可以就扩大范围
    }
    printf("%d",l);
}
请勿抄袭

END

]]>