题意：给一个有向无环图，求最大的点集，x不能到y，且y不能到x。
题解：首先可以知道的是这个是偏序集最大独立集，通过Dilworth定理可以知道是要求最小链划分（最小可交路径覆盖），我们通过网络流优化，建边类似于二分图最小路径覆盖，将所有点拆分为x与x+n，源点连接x,x+n连接汇点，由于是可交路径，所以再建立x+n到x的路径使得路径可交。
AC代码：
#include<cstdio> #include<cstring> #include<queue> #include<cmath> using namespace std; const int Ni = 200005; const int MAX = 1<<28; struct Edge{ int u,v,c; int next; }edge[2000005]; int n,m; int edn;//边数 int p[Ni];//父亲 int d[Ni]; int sp,tp;//原点，汇点 void addedge(int u,int v,int c) { edge[edn].u=u; edge[edn].v=v; edge[edn].c=c; edge[edn].next=p[u]; p[u]=edn++; edge[edn].u=v; edge[edn].v=u; edge[edn].c=0; edge[edn].next=p[v]; p[v]=edn++; } int bfs() { queue <int> q; memset(d,-1,sizeof(d)); d[sp]=0; q.push(sp); while(!q.empty()) { int cur=q.front(); q.pop(); for(int i=p[cur];i!=-1;i=edge[i].next) { int u=edge[i].v; if(d[u]==-1 && edge[i].c>0) { d[u]=d[cur]+1; q.push(u); } } } return d[tp] != -1; } int dfs(int a,int b) { int r=0; if(a==tp)return b; for(int i=p[a];i!=-1 && r<b;i=edge[i].next) { int u=edge[i].v; if(edge[i].c>0 && d[u]==d[a]+1) { int x=min(edge[i].c,b-r); x=dfs(u,x); r+=x; edge[i].c-=x; edge[i^1].c+=x; } } if(!r)d[a]=-2; return r; } int dinic(int sp,int tp) { int total=0,t; while(bfs()) { while(t=dfs(sp,MAX)) total+=t; } return total; } int main() { int i,u,v,c; int T; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); edn=0;//初始化 memset(p,-1,sizeof(p)); sp=0;tp=2*n+1; for(i=1;i<=n;i++){addedge(sp,i,1);addedge(i+n,tp,1);addedge(i+n,i,MAX);} for(i=0;i<m;i++) { scanf("%d%d",&u,&v); addedge(u,v+n,MAX); } printf("%d\n",n-dinic(sp,tp)); } return 0; }