[1143] [CTSC2008]祭祀river（最大独立集 || 偏序集最大反链）

传送门

网上说这是偏序集最大反链，然而我实在不理解。

所以我换了一个思路，先用floyd，根据点的连通性连边，

问题就转换成了找出最多的点，使任意两个点之间不连边，也就是最大独立集。

——代码

1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 5 const int MAXN = 101; 6 int n, m, ans, cnt; 7 int a[MAXN][MAXN], belong[MAXN], head[MAXN], to[MAXN << 6], next[MAXN << 6]; 8 bool vis[MAXN]; 9 10 inline int read() 11 18 19 inline bool find(int u) 20 33 } 34 } 35 return 0; 36 } 37 38 inline void add(int x, int y) 39 44 45 int main() 46 56 for(k = 1; k <= n; k++) 57 for(i = 1; i <= n; i++) 58 for(j = 1; j <= n; j++) 59 a[i][j] |= (a[i][k] && a[k][j]); 60 memset(head, 1, sizeof(head)); 61 for(i = 1; i <= n; i++) 62 for(j = 1; j <= n; j++) if(a[i][j]) 64 add(i, j); 65 ans = n; 66 for(i = 1; i <= n; i++) 67 71 printf("%d\n", ans); 72 return 0; 73 }
View Code

上一篇：[luoguP2709] 小B的询问（莫队）

下一篇：[luoguP1962] 斐波那契数列（矩阵快速幂）

---

二分图 Floyd 最大独立集 匈牙利算法