【二分图+有难度】杭电 hdu 1281 棋盘游戏
/* THE PROGRAM IS MADE BY PYY *//*----------------------------------------------------------------------------// Copyright (c) 2011 panyanyany All rights reserved. URL : http://acm.hdu.edu.cn/showproblem.php?pid=1281 Name: 1281 棋盘游戏 Date: Tuesday, November 8, 2011 Time Stage : an hour Result: 49302812011-11-08 20:57:47Accepted128131MS248K1675 BC++pyyTest Data :Review :一开始想不明白，怎么样才能求那些“重要点”，甚至还想到从反面下手，先求“不重要点”。但还是不得其解，于是看了人家的解题报告，发现可以试着删除某个点，如果删除后最大的“车”数量有所减少，则证明它是“重要点”。//----------------------------------------------------------------------------*/#include <stdio.h>#include <vector>using std::vector ;#define MAXSIZE 109intn, m, k ;intlink, cover ;boolmap ;int find (int cur){int i, j ;for (i = 1 ; i <= m ; ++i){if (cover == false && map == true){cover = true ;if (link == 0 || find (link)){link = cur ;return 1 ;}}}return 0 ;}int getSum (){int i ;int sum ;sum = 0 ;memset (link, 0, sizeof (link)) ;for (i = 1 ; i <= n ; ++i){memset (cover, 0, sizeof (cover)) ;sum += find (i) ;}return sum ;}int main (){int i, j ;int x, y ;int sum, tmpSum, important, tcase ;tcase = 0 ;while (~scanf ("%d%d%d", &n, &m, &k)){memset (map, false, sizeof (map)) ;for (i = 0 ; i < k ; ++i){scanf ("%d%d", &x, &y) ;map = true ;}sum = getSum () ;// 枚举所有可落“车”的点，分别删除，若车的最大数减少，则证明// 该点为 “重要点”important = 0 ;for (i = 1 ; i <= n ; ++i){for (j = 1 ; j <= m ; ++j){if (map){map = false ;tmpSum = getSum () ;map = true ;if (tmpSum < sum)++important ;}}}printf ("Board %d have %d important blanks for %d chessmen.\n", ++tcase,important, sum) ;}return 0 ;}
页:
[1]