首页 > 代码库 > [1143] [CTSC2008]祭祀river（最大独立集 || 偏序集最大反链）
[1143] [CTSC2008]祭祀river（最大独立集 || 偏序集最大反链）
传送门
网上说这是偏序集最大反链，然而我实在不理解。
所以我换了一个思路，先用floyed，根据点的连通性连边，
问题就转换成了找出最多的点，使任意两个点之间不连边，也就是最大独立集。
——代码
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 {12 int x = 0;13 char c = getchar();14 for(; !isdigit(c); c = getchar());15 for(; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + c - ‘0‘;16 return x;17 }18 19 inline bool find(int u)20 {21 int i, v;22 for(i = head[u]; i ^ -1; i = next[i])23 {24 v = to[i];25 if(!vis[v])26 {27 vis[v] = 1;28 if(!belong[v] || find(belong[v]))29 {30 belong[v] = u;31 return 1;32 }33 }34 }35 return 0;36 }37 38 inline void add(int x, int y)39 {40 to[cnt] = y;41 next[cnt] = head[x];42 head[x] = cnt++;43 }44 45 int main()46 {47 int i, j, k, x, y;48 n = read();49 m = read();50 for(; m--;)51 {52 x = read();53 y = read();54 a[x][y] = 1;55 }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++)63 if(a[i][j])64 add(i, j);65 ans = n;66 for(i = 1; i <= n; i++)67 {68 memset(vis, 0, sizeof(vis));69 ans -= find(i);70 }71 printf("%d\n", ans);72 return 0;73 }
[1143] [CTSC2008]祭祀river（最大独立集 || 偏序集最大反链）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。