偏序集的最大反鏈【二分圖】
在有向無環圖中，有如下的一些定義和性質：
鏈：一條鏈是一些點的集合，鏈上任意兩個點x, y，滿足要么 x 能到達 y ，要么 y 能到達 x 。
反鏈：一條反鏈是一些點的集合，鏈上任意兩個點x, y，滿足 x 不能到達 y，且 y 也不能到達 x。
又有諸如以下定理：
一、有向無環圖最小不相交路徑覆蓋
定義：用最少的不相交路徑覆蓋所有頂點。
定理：把原圖中的每個點V拆成Vx和Vy，如果有一條有向邊A->B，那么就加邊Ax-By。這樣就得到了一個二分圖，最小路徑覆蓋=原圖的節點數-新圖最大匹配。
簡單證明：一開始每個點都獨立的為一條路徑，總共有n條不相交路徑。我們每次在二分圖里加一條邊就相當于把兩條路徑合成了一條路徑，因為路徑之間不能有公共點，所以加的邊之間也不能有公共點，這就是匹配的定義。所以有：最小路徑覆蓋=原圖的節點數-新圖最大匹配。
二、有向無環圖最小可相交路徑覆蓋
定義：用最小的可相交路徑覆蓋所有頂點。
算法：先用floyd求出原圖的傳遞閉包，即如果a到b有路，那么就加邊a->b。然后就轉化成了最小不相交路徑覆蓋問題。
三、偏序集的最大反鏈
定義：偏序集中的最大獨立集。
Dilworth定理：對于任意偏序集都有，最大獨立集(最大反鏈)=最小鏈的劃分(最小可相交路徑覆蓋).
通過Dilworth定理, 我們就可以把偏序集的最大獨立集問題轉化為最小可相交路徑覆蓋問題了。
經典例題：
BZOJ 1143祭祀river
#include<bits/stdc++.h> using namespace std; const int MAXN=105; int g[MAXN][MAXN]; int uN,vN; int linker[MAXN]; bool used[MAXN]; bool dfs(int u) { for(int v = 0; v < vN; v++) if(g[u][v] && !used[v]) { used[v] = true; if(linker[v] == -1 || dfs(linker[v])) { linker[v] = u; return true; } } return false; } int hungary() { int res = 0; memset(linker,-1,sizeof(linker)); for(int u = 0; u < uN; u++) { memset(used,false,sizeof(used)); if(dfs(u))res++; } return res; } int main() { int n,m; while (~scanf("%d%d",&n,&m)) { memset(g,0,sizeof(g)); for (int i=1; i<=m; i++) { int u,v; scanf("%d%d",&u,&v); g[u-1][v-1]=1; } for (int k=0; k<n; k++) for (int i=0; i<n; i++) for (int j=0; j<n; j++) if (g[i][k] && g[k][j]) g[i][j]=1; uN=vN=n; printf("%d\n",n-hungary()); } return 0; }
浙公網安備 33010602011771號