题目大意：在一个n ＊ m的地图上面有k个垃圾，问需要派几个机器人才能全部捡完。 机器人的行走路线已经被规划好了，只能从左上向右下走，且只能前进，不能倒退
解题思路：将所有点分成两个点集，，点集之间的关系就是能否从该点走到另外一点，如果可以的话，那么关系就存在了
;const int N = 1000;struct point {int x, y;}P[N];int vis[N], link[N], cnt;vector<int> g[N];bool judge(point a, point b) {if(b.y >= a.y && b.x >= a.x)return true;return false;}void init() {cnt = 1;while(scanf(“%d%d”, &P[cnt].x, &P[cnt].y)) {if(P[cnt].x == 0 && P[cnt].y == 0)break;cnt++;}for(int i = 0; i < cnt; i++) {g[i].clear();for(int j = 0; j < cnt; j++) {if(i != j && judge(P[i], P[j]))g[i].push_back(j);}}memset(link, -1, sizeof(link));}bool dfs(int u) {for(int i = 0; i < g[u].size(); i++) {int v = g[u][i];if(vis[v])continue;vis[v] = 1;if(link[v] == -1 || dfs(link[v])) {link[v] = u;return true;}}return false;}void hungary() {int ans = 0;for(int i = 0; i < cnt; i++) {memset(vis, 0 ,sizeof(vis));if(dfs(i))ans++;}printf(“%d\n”, cnt – ans);}int main() {while(scanf(“%d%d”, &P[0].x, &P[0].y) != EOF) {if(P[0].x == -1 && P[0].y == -1)break;if(P[0].x == 0 && P[0].y == 0) {printf(“0\n”);continue;}init();hungary();}return 0;}
也许这就是一个人无法抗拒的命运，有你、有我、也有他。
