挺经典的一道题 题意：给你dag,求最长反链(包括给出一个构造)，以及哪些点可以成为最长反链上的点 解法:第一问（反链大小）和第三问 最长反链=最小链覆盖 最小链覆盖=dag扩充完以后的最小路径覆盖 "dag的扩充"指通过该dag,i可以到达j，则连i->j 最小路径覆盖=V-拆点二分图最大匹配 从out连去in 我们来做第二问 注意到，最长反链实际上就是dag扩充后的最大独立集，我们尝试求出dag扩充后的最小点覆盖 首先你要了解求解二分图的最小点覆盖 我们在拆点的图上求出二分图的最小点覆盖，那么即为拆点二分图最大匹配m 对应到原图(指dag扩充后的)中的点，实际上相当于我们选了不超过m个点，成为最小点覆盖 不可能小于m，所以我们就求出了大小为m的最小点覆盖 剩下的即是最长反链 匈牙利跑得真快
#include<bits/stdc++.h> using namespace std; int n,m,Ans; #define V 105 #define E 100010 int ans1[V],ans2[V]; bool rel[V][V]; int vis[V<<1],T=0; vector<int> vec[V<<1]; int match[V<<1]; int head[V<<1],v[E],nxt[E],tot=0; inline void add_edge(int s,int e){tot++;v[tot]=e;nxt[tot]=head[s];head[s]=tot;} bool dfs(int u){ for(int i=head[u];i;i=nxt[i]) if(vis[v[i]]^T){ vis[v[i]]=T; if(!match[v[i]]||dfs(match[v[i]])){ match[u]=v[i]; match[v[i]]=u; return true; } } return false; } int id[V],cnt; int calc(int u){ cnt=0; memset(id,0,sizeof(int)*(n+1)); tot=0; for(int i=1;i<=n;++i) if(rel[i][u]||rel[u][i])id[i]=-1; for(int i=1;i<=n;++i) if(!id[i])id[i]=++cnt; memset(head,0,sizeof(int)*(cnt+1)); for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) if(j!=i&&id[i]!=-1&&id[j]!=-1&&rel[i][j])add_edge(id[i],id[j]+cnt); for(int i=1;i<=cnt*2;++i)match[i]=0; int res=1+cnt; for(int i=1;i<=cnt;++i) if(!match[i]){ T++; res-=dfs(i); } return res; } void Dfs(int u){ vis[u]=T; for(int i=head[u];i;i=nxt[i]) if(vis[v[i]]^T){ vis[v[i]]=T; Dfs(match[v[i]]); } } void search(int u,int fr){ vis[u]=T; rel[fr][u]=true; for(int i=0;i<vec[u].size();++i) if(vis[vec[u][i]]^T)search(vec[u][i],fr); } int main(){ cin>>n>>m; int s,e; for(int i=1;i<=m;++i){ cin>>s>>e; vec[s].push_back(e); } for(int i=1;i<=n;++i){ T++; search(i,i); } for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) if(i!=j&&rel[i][j])add_edge(i,j+n); Ans=n; for(int i=1;i<=n;++i) if(!match[i]){ T++; Ans-=dfs(i); } T++; for(int i=1;i<=n;++i) if(!match[i])Dfs(i); for(int i=1;i<=n;++i) if(vis[i]==T&&vis[i+n]!=T)ans1[i]=1; for(int i=1;i<=n;++i) if(calc(i)==Ans)ans2[i]=1; printf("%d\n",Ans); for(int i=1;i<=n;++i)printf("%d",ans1[i]);puts(""); for(int i=1;i<=n;++i)printf("%d",ans2[i]);puts(""); return 0; }