即等价于选出最多的一组点，使得其中不存在祖先关系。 这样就转化为了一个经典的最长反链问题,首先建立传递闭包 然后我们这样建立一张二分图：将原图拆点,每个点x拆成x和x′,形成一张二分图 若原图中有一条路径从 x 到y，则在二分图中建立 (u,v′) 这样一条边 答案即为 n 减去最大匹配数。 因为匹配数即为最小链数，而最长反链=n−最小链数 因此该方法可行 代码如下：
#include<bits/stdc++.h> using namespace std; #define M 55 char str[M]; vector<int>edge[M]; int mark[M<<1],to[M<<1],ok[M][M]; int n; bool dfs(int x){ for(int i=0;i<edge[x].size();i++){ int y=edge[x][i]; if(mark[y])continue; mark[y]=1; if(!to[y]||dfs(to[y])){ to[y]=x; return true; } } return false; } int solve(){ int res=0; memset(to,0,sizeof(to)); for(int i=1;i<=n;i++){ memset(mark,0,sizeof(mark)); res+=dfs(i); } return res; } int main(){ scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%s",str+1); for(int j=1;j<=n;j++) if(str[j]=='Y'){ ok[i][j]=1; edge[i].push_back(j+n); } } for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(ok[i][k]&&ok[k][j]&&!ok[i][j]){ ok[i][j]=1; edge[i].push_back(j+n); } printf("%d\n",n-solve()); return 0; }