直接搞。 想麻烦 也可以伞兵那样搞 ， 最小割网络流，把权值全置为1. 估计会超时。。
#include <cstdio> #include <cstring> #include <algorithm> #include <climits> #include <string> #include <iostream> #include <map> #include <cstdlib> #include <list> #include <set> #include <queue> #include <stack> #include<math.h> using namespace std; const int maxn= 555; int link[maxn]; int Map[maxn][maxn]; int n; const int INF=0xfffffff; int used[maxn]; int dfs(int x) { for(int i=1;i<=n;i++){ if(!used[i]&&Map[x][i]){ used[i]=1; if(link[i]==-1||dfs(link[i])){ link[i]=x; return 1; } } } return 0; } void gao() { int ans=0; memset(link,-1,sizeof(link)); for(int i=1;i<=n;i++){ memset(used,0,sizeof(used)); if(dfs(i)) ans+=1; } cout<<ans<<endl; } int main() { int k; while(scanf("%d%d",&n,&k)!=EOF){ memset(Map,0,sizeof(Map)); for(int i=0;i<k;i++){ int a;int b; scanf("%d%d",&a,&b); Map[a][b]=1; } gao(); } return 0; }