BZOJ.4160.[NEERC2009]Exclusive Access 2(状压DP Dilworth定理)

news/2024/12/12 6:16:49/

BZOJ


DAG中,根据\(Dilworth\)定理,有 \(最长反链=最小链覆盖\),也有 \(最长链=最小反链划分数-1\)(这个是指最短的最长链?并不是很确定=-=),即把所有点划分成最少的集合,使得集合内的点两两之间没有边。
直接状压。设\(f[s]\)表示\(s\)集合内的点是否满足两两之间没有边,\(g[s]\)表示最少可以将\(s\)划分为几个集合使得集合内两两没有边。
那么如果\(f[s']=1\ (s'\in s)\)\(g[s]=\min(g[s],\ g[s\ \text{xor}\ s']+1)\)
复杂度\(O(m2^n+3^n)\)

这么做不需要考虑给边定向啊= =
另一个这样应用\(Dilworth\)定理的好像是导弹拦截问题?

所以这题猜个结论之后,不和BZOJ4145一样吗=v=


//1112kb    728ms
#include <cstdio>
#include <cstring>
#include <algorithm>
#define lb(x) (x&-x)
const int N=15,M=(1<<N)+1;int g[M],id[233],ref[M];
bool mp[N][N],f[M];int main()
{char s1[3],s2[3];memset(id,0xff,sizeof id);int n=0,m; scanf("%d",&m);for(int p1,p2; m--; ){scanf("%s%s",s1,s2);if(id[p1=s1[0]]==-1) id[p1]=n++;if(id[p2=s2[0]]==-1) id[p2]=n++;mp[id[p1]][id[p2]]=1, mp[id[p2]][id[p1]]=1;}int lim=(1<<n)-1;for(int i=0; i<n; ++i) ref[1<<i]=i;for(int s=0; s<=lim; ++s){f[s]=1;for(int s1=s; s1&&f[s]; s1^=lb(s1))for(int s2=s,i=ref[lb(s1)]; s2; s2^=lb(s2))if(mp[i][ref[lb(s2)]]) {f[s]=0; break;}}g[0]=0;for(int s=1; s<=lim; ++s){int tmp=1<<30;for(int ss=s; ss; ss=(ss-1)&s)if(f[ss]) tmp=std::min(tmp,g[s^ss]+1);g[s]=tmp;}printf("%d\n",g[lim]-2);return 0;
}

转载于:https://www.cnblogs.com/SovietPower/p/10754314.html


http://www.ppmy.cn/news/325674.html

相关文章

luogu P4160 [SCOI2009]生日快乐

传送门 考虑因为每个人的蛋糕体积要相等,如果切了一刀,那么要使得分当前蛋糕的人根据分成的两部分蛋糕的体积分成两部分人,所以假设当前有n人,切的这一刀要是在x或y的\(\frac{k}{n}(k\in N_,k\in [1,n])\)处,然后两边分别有\(k\)和\(n-k\)个人分,所以分治做下去救星了 更多内容…

2023-06-11 LeetCode每日一题(从链表中删去总和值为零的连续节点)

2023-03-29每日一题 一、题目编号 1171. 从链表中删去总和值为零的连续节点二、题目链接 点击跳转到题目位置 三、题目描述 给你一个链表的头节点 head&#xff0c;请你编写代码&#xff0c;反复删去链表中由 总和 值为 0 的连续节点组成的序列&#xff0c;直到不存在这样…

[BZOJ]4160: [Neerc2009]Exclusive Access 2 状压DP+Dilworth定理

Description 给出 N 个点M 条边的无向图&#xff0c;定向得到有向无环图&#xff0c;使得最长路最短。 N ≤ 15, M ≤ 100 Solution 大家都知道Dilworth定理的其中一个内容&#xff1a;最小路径覆盖最长反链。 实际上与之相似的是&#xff1a;最长路最小反链划分数。 这个东…

P4160 [SCOI2009]生日快乐

传送门 一看 $n$ 这么小&#xff0c;搜就完事了... 因为最后每块小蛋糕面积固定&#xff0c;所以每次切完面积都必须是小蛋糕面积的倍数 那么最多只有第一次有 $10$ 个位置&#xff0c;之后越来越少&#xff0c;复杂度很低 然后注意不要乱剪枝...&#xff0c;每次切不一定只切长…

hdu4160 Dolls

http://www.elijahqi.win/2017/12/31/hdu4160-dolls/ ‎ Problem Description Do you remember the box of Matryoshka dolls last week? Adam just got another box of dolls from Matryona. This time, the dolls have different shapes and sizes: some are skinny, some…

hdoj 4160 Dolls

http://acm.hdu.edu.cn/showproblem.php?pid4160 转化为二分图的最小路径覆盖问题。 那么答案就是n-最大匹配数 View Code #include<iostream> #include<string.h> #include<algorithm> #include<stdio.h> #include<vector> #define maxn 1000…

BZOJ4160 [Neerc2009]Exclusive Access 2 题解(Dilworth定理+状压DP)

题目&#xff1a;BZOJ4160. 题目大意&#xff1a;给定一张 n n n个点 m m m条边无向图&#xff0c;要求给每条边定向&#xff0c;求定向后有向图上的最长路最短是多少. 1 ≤ n ≤ 15 , 1 ≤ m ≤ 100 1\leq n\leq 15,1\leq m\leq 100 1≤n≤15,1≤m≤100. 首先&#xff0c;最…

hdu4160

/* 分析&#xff1a; 哎呀&#xff0c;在用C提交ac的里面竟然排第一呀&#xff0c;so~吃惊呀~ 最小路径覆盖&#xff0c;如果i可以放到j里面&#xff0c;那么就构建一条 i到j的有向边。 2012-07-14 */ #include"stdio.h" #include"string.h"struct A {int …