[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
下一篇：[luoguP1962] 斐波那契数列（矩阵快速幂）
二分图 Floyd 最大独立集 匈牙利算法
spc文件怎么看，spc文件用什么打开？
0文件怎么看，0文件用什么打开？
sparseimage文件怎么看，sparseimage文件用什么打开？
sp文件怎么看，sp文件用什么打开？
dv文件怎么看，dv文件用什么打开？
soundpack文件怎么看，soundpack文件用什么打开？
dus文件怎么看，dus文件用什么打开？
dtw文件怎么看，dtw文件用什么打开？
spdf文件怎么看，spdf文件用什么打开？
0文件怎么看，0文件用什么打开？