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

總結

以上是生活随笔為你收集整理的BZOJ.4160.[NEERC2009]Exclusive Access 2(状压DP Dilworth定理)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。