首页 > 代码库 > BZOJ 1143 祭祀 river（最大独立集）
BZOJ 1143 祭祀 river（最大独立集）
题目链接：http://61.187.179.132/JudgeOnline/problem.php?id=1143
题意：给出一个有向无环图。在其中找出一个最大的点集使得点集中任意两个点之间不可达。
思路：首先在给出图中跑一次floyd，这样g[i][j]=1则i可到达j。那么题意就是求最大独立集。最大独立集=|G|-最小顶点覆盖=|G|-二分图最大匹配。
int g[N][N],match[N],visit[N];int n;int DFS(int u){ int i; FOR1(i,n) if(!visit[i]&&g[u][i]) { visit[i]=1; if(match[i]==-1||DFS(match[i])) { match[i]=u; return 1; } } return 0;}int m;int main(){ RD(n,m); int i,x,y; FOR1(i,m) { RD(x,y); g[x][y]=1; } int j,k; FOR1(k,n) FOR1(i,n) FOR1(j,n) if(g[i][k]&&g[k][j]) { g[i][j]=1; } clr(match,-1); int ans=0; FOR1(i,n) { clr(visit,0); if(DFS(i)) ans++; } PR(n-ans);}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。