题目：飞行员配对(二分图最大匹配)
总结：匈牙利算法的模板。结合代码看注释，可以模拟一遍
#include <stdio.h> #include <vector> #include <string.h> using namespace std; const int N = 205; int vis[N];// int pre[N];//pre[x] = y;表示x和y为一对匹配点，y是起点，x是终点 vector<int>G[N]; int n,m; bool dfs(int u){ for(int i = 0;i < G[u].size();i++){ int v = G[u][i];//和u相匹配的点 if(!vis[v]){//表示在这一轮，还没有被访问到， vis[v] = 1;//表示已经访问到了 if(!pre[v] || dfs(pre[v])){//如果这个v点之间没有和它匹配的，那么就直接连起来 //否则就从这个起点再往前推， pre[v] = u; return true;//表示这一段可以成立 } } } return false; } void solve(){ int ans = 0; for(int i = 1;i <= n;i++){//进行逐一的遍历 memset(vis,0,sizeof vis);//每一轮开启一个新的标记点 if(dfs(i)) ans++;//表示以i为起点的是可以放下的 } printf("%d\n",ans); } void init(){ for(int i = 0;i < N;i++){ G[i].clear(); } memset(pre,0,sizeof pre); } int main(){ scanf("%d%d",&n,&m); int x,y; while(scanf("%d%d",&x,&y)&&(x != -1 && y != -1)){ G[x].push_back(y); } solve(); return 0; }