题目链接
第一次提交的时候用的是邻接矩阵，因为我看测试数据不多，n<=500,没有考虑到时间问题，超时了。。
思路：邻接表+匈牙利算法
#include<stdio.h> #include<vector> #include<string.h> using namespace std; //int e[505][505]; int match[505]; int book[505]; int n,m; vector<int>e[505]; bool dfs(int u) { int i,v; for(v=0;v<e[u].size();v++) { i=e[u][v]; if(!book[i]) { book[i]=1; if(match[i]==0 || dfs(match[i])) { match[i]=u; return true; } } } return false; } int main() { int T; scanf("%d",&T); while(T--) { int i,j,t1,t2,sum=0; scanf("%d%d",&n,&m); for(i=0;i<=n;i++) e[i].clear(); for(i=1;i<=m;i++) { scanf("%d%d",&t1,&t2); //e[t1][t2]=1; e[t1].push_back(t2); } memset(match,0,sizeof(match)); for(i=1;i<=n;i++) { memset(book,0,sizeof(book)); if(dfs(i)) sum++; } printf("%d\n",sum); } return 0; }