【二分图+最小路径覆盖+建图难度】北大 poj 1548 Robots
/* THE PROGRAM IS MADE BY PYY *//*----------------------------------------//Copyright (c) 2011 panyanyany All rights reserved.URL : http://poj.org/problem?id=1548Name : 1548 RobotsDate : Wednesday, November 30, 2011Time Stage : two hoursResult: Test Data :Review :这题比较有难度，一开始确实不知道怎么建图……或者说是想得很繁杂，而且还不断WA。参考了大牛的代码后, 幡然醒悟，而且还学到了一种特殊的建图方法，嗯，确实很与众不同。但要想真正消化吸收，恐怕还是要再做多一两次的。大牛位置：nizhenyang的博客：http://blog.163.com/zjut_nizhenyang/blog/static/169570029201011113748927///----------------------------------------*/#include <stdio.h>#include <string.h>#include <vector>using namespace std ;#define MAXSIZE(25*25)intcnt ;boolcover[MAXSIZE], graph[MAXSIZE][MAXSIZE] ;intlink[MAXSIZE] ;struct POINT {POINT (int b = 0, int a = 0): y(b), x(a) {}POINT (const POINT &pt): y(pt.y), x(pt.x) {}int x, y ;};bool find (int cur){int i, j ;for (i = 0 ; i < cnt ; ++i){if ((cover[i] == false) && (graph[cur][i] == true)){cover[i] = true ;if ((link[i] == -1) || find (link[i])){link[i] = cur ;return true ;}}}return false ;}int main (){int i, j ;int x, y ;int sum ;while (1){vector<POINT> map ;scanf ("%d%d", &y, &x) ;if ((y == -1) && (x == -1))break ;map.push_back (POINT (y, x)) ;while (scanf ("%d%d", &y, &x), y | x){map.push_back (POINT (y, x)) ;}cnt = map.size () ;memset (graph, false, sizeof (graph)) ;for (i = 0 ; i < cnt ; ++i){for (j = i + 1 ; j < cnt ; ++j){// 必须为 <=，因为有可能是(1, 2), (1, 3)两个点有垃圾// 即，下一个有垃圾的点，有可能位于同行或同列if ((map[i].y <= map[j].y) && (map[i].x <= map[j].x))graph[i][j] = true ;}}sum = 0 ;memset (link, -1, sizeof (link)) ;for (i = 0 ; i < cnt ; ++i){memset (cover, 0, sizeof (cover)) ;sum += find (i) ;}printf ("%d\n", cnt - sum) ;}return 0 ;}?