开始读题没理解题意，以为就是覆盖，可是怎么交都不对。。。 我就气愤了，结果去百度了一下发现奶奶的这题的机器人是可以隔点瞭望的，例如1->2->3、2->4、5->2 这个图 我现在5匹配2，2匹配4，那么1和3就剩下了，结果就是需要三个机器人。可是这与题意是相悖的，提议要求可一隔点向往，也就是说1能看到3，那么1和3也是可以匹配的，所以答案是2。（有向图的匹配和无向图的匹配是不一样的）
那么接下来的任务就简单了，我把所有间接到达的点全部变成直接到达，让他自己去随便匹配好了，答案一定是对的。
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<vector> 5 #define maxn 510 6 7 using namespace std; 8 9 vector<int> g[maxn]; 10 int group[maxn][maxn]; 11 int link[maxn],vis[maxn]; 12 int n,m; 13 14 int dfs(int x) 15 { 16 for(int i=0;i<g[x].size();i++) 17 { 18 int e=g[x][i]; 19 if(!vis[e]) 20 { 21 vis[e]=1; 22 if(link[e]==-1||dfs(link[e])) 23 { 24 link[e]=x; 25 return true; 26 } 27 } 28 } 29 return false; 30 } 31 void floyd() 32 { 33 for(int i=1;i<=n;i++) 34 { 35 for(int j=1;j<=n;j++) 36 { 37 for(int k=1;k<=n;k++) 38 { 39 if(group[k][i]&&group[i][j]&&j!=k) group[k][j]=1; 40 } 41 } 42 } 43 } 44 void setup_map() 45 { 46 for(int i=1;i<=n;i++) 47 { 48 for(int j=1;j<=n;j++) 49 { 50 if(group[i][j]) 51 g[i].push_back(j); 52 } 53 } 54 } 55 int main() 56 { 57 while(scanf("%d%d",&n,&m)!=EOF) 58 { 59 if(n==0&&m==0) break; 60 for(int i=1;i<=n;i++) 61 g[i].clear(); 62 memset(group,0,sizeof(group)); 63 for(int j=1;j<=m;j++) 64 { 65 int a,b; 66 scanf("%d%d",&a,&b); 67 group[a][b]=1; 68 } 69 floyd(); 70 setup_map(); 71 memset(link,-1,sizeof(link)); 72 int sum=0; 73 for(int q=1;q<=n;q++) 74 { 75 memset(vis,0,sizeof(vis)); 76 if(dfs(q)) sum++; 77 } 78 printf("%d ",n-sum); 79 } 80 return 0; 81 }