题目大意：
从有向无环图中选出若干点不想交的链，使得这些链覆盖所有的点，并且链的条数最小。
思路：
设超级源点$S$、超级汇点$T$。
将$N$个点复制一份，分为$A$部和$B$部。
对于$A$部的所有点$A_i$，连一条从$S$到$A_i$的边；
对于$B$部的所有点$B_i$，连一条从$B_i$到$T$的边。
用最大流跑一边二分图匹配，得到的最大流F为每条链上入度为0的点的个数总和，而B部中未被匹配的点对应着每个链的头。
答案即为N-F。
1 #include<queue> 2 #include<cstdio> 3 #include<cctype> 4 #include<vector> 5 #include<cstring> 6 inline int getint() { 7 char ch; 8 while(!isdigit(ch=getchar())); 9 int x=ch^'0'; 10 while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0'); 11 return x; 12 } 13 int s,t; 14 const int E=42000,V=1002; 15 struct Edge { 16 int from,to; 17 bool remain; 18 }; 19 Edge e[E]; 20 std::vector<int> g[V]; 21 int sz=0; 22 inline void add_edge(const int u,const int v,const bool w) { 23 e[sz]=(Edge){u,v,w}; 24 g[u].push_back(sz); 25 sz++; 26 } 27 int p[V]; 28 bool a[V]; 29 inline bool Augment() { 30 memset(a,0,sizeof a); 31 a[s]=true; 32 std::queue<int> q; 33 q.push(s); 34 while(!q.empty()&&!a[t]) { 35 int x=q.front(); 36 q.pop(); 37 for(unsigned i=0;i<g[x].size();i++) { 38 Edge &y=e[g[x][i]]; 39 if(!a[y.to]&&y.remain) { 40 p[y.to]=g[x][i]; 41 a[y.to]=a[x]&&y.remain; 42 q.push(y.to); 43 } 44 } 45 } 46 return a[t]; 47 } 48 inline int EdmondsKarp() { 49 int maxflow=0; 50 while(Augment()) { 51 for(int i=t;i!=s;i=e[p[i]].from) { 52 e[p[i]].remain^=true; 53 e[p[i]^1].remain^=true; 54 } 55 maxflow++; 56 } 57 return maxflow; 58 } 59 int main() { 60 int n=getint(),m=getint(); 61 s=0,t=n<<1|1; 62 for(int i=1;i<=n;i++) { 63 add_edge(s,i,true); 64 add_edge(i,s,false); 65 add_edge(n+i,t,true); 66 add_edge(t,n+i,false); 67 } 68 for(int i=1;i<=m;i++) { 69 int u=getint(),v=getint(); 70 add_edge(u,n+v,true); 71 add_edge(n+v,u,false); 72 } 73 printf("%d ",n-EdmondsKarp()); 74 return 0; 75 }