HDU2819Swap(二分图最大匹配)

题目链接  http://acm.hdu.edu.cn/showproblem.php?pid=2819

题目大意很明确,交换图的某些行或者是某些列(可以都换),使得这个N*N的图对角线上全部都是1.

这里有一点需要说明,就是说题目的交换,其实是将原来图的某一行移到最后图的某一行,而不是指先交换两行,得到一个新图,再交换新图的两行。感觉这里比较坑。

这里先说明的一点就是,如果通过交换某些行没有办法的到解的话,那么只交换列 或者 既交换行又交换列 那也没办法得到解。其实个人感觉这个可以用矩阵的秩来解释,所有的对角线都是1,所以也就是矩阵的秩就是N,所以秩小于N就无解。另外,根据矩阵的性质,任意交换矩阵的两行  或者  两列,矩阵的秩不变,也就保证了如果通过 只交换行  或  只交换列 无法得到解的话,那么其他交换形式也必然无解。

既然说是用二分图的最大匹配,那怎么构建二分图呢,我们构建的二分图,第一部分X表示的是横坐标,第二部分Y表示纵坐标,所以范围都是1~N,然后如果a[i][j]是1,那我们就从X的i向Y的j引一条边,那么这条边的含义就可以解释为可以将Y的第j列(因为Y表示的是列的集合)移到第i列,使得a[i][i]变成1,这样就相当于是第i行第i列就变成了1,也就是说对角线多了一个1。

因此我们求这个二分图的最大匹配(目的是为了让每一列只与X中的某一行匹配),这样来就形成了N条边,那我们只需要将所有匹配的边的右边(列)  和  左边(行)所在的列  交换,这样一来对角线上这一行就成了1.

上面也也正好提示了如果最大匹配是N,那就存在解,否则无解。

aaarticlea/png;base64,iVBORw0KGgoAAAANSUhEUgAABJMAAAA6CAIAAACLTY/mAAAZzUlEQVR4nO1dS27cxtrlOrQMdS8i3oMHsnsF9tBA5pHsnsaAvYdfyr1qeBB4LiATObKjXw3YgyCABh5oEjff5B0UWaw3q9ikWGSfgw+JxSaLxY+nvqpTLwblQaIoiizLkiSJoigMwzAM4zhO0zTP86IGezI5PmKGgVkCPAR8AHgI+ADwEPAB4CHgAww8DMbO2zjI8zyO46hGkiRZlpGyJ5dMABgI4CHgA8BDwAeAh4APAA8BH2DgYXD09ArGGimWo2cD5oOR8jN6NmCwR7AwDKMoGj0bnY1WeKPnxDeDW+BS+Mdng7tgTgblJhqKEIwayAA7HCOTMUbPRmeDcjN7ZvRszMngUvgH7oKNZVBuoqEIwaiBDLDDMTIfY/RsdDYoN7NnRs/GnAwuhX/gLthYBuUmGooQjBrIADsci+M4y7LRs9HZoNzMnhk9G3MyuBT+gbtgYxmUm2goQjBqIAPscCxJkjzPR89GZ4NyM3tm9GzMyeBS+Afugo1lUG6ioQjBqIEMsMOxNE0nvTkTlJvZM6NnY04Gl8I/cBdsLINyEw1FCEYNZIAdjiVJAuU2S4Nb4FL4x2eDu2BOBuUmGooQjBrIADsci+MYsyVnaXALXAr/+GxwF8zJelFuXz+WMh5e9pZLkj5JUHGvj+/79Ih/RYh55Pv7J+3n37y738f/rLevjp5evbxWepjcRcL1g3D5pM0/MjymiUxwuMqKqK45URQBDTlFszztwM1uh5IhInA/EZ6e735rAeG7n/f3p0cR0tEtj+GTbx9u6PEnH0Jl6fbZ9mQa+/huKTi56Of7byN51d0/Y+Z2dOvirslYXeqvv9pfxVTZezZo52nDKbceS2BLvd41DqrNsyIkPW87+/sk+svrslS3nHTtEofC6b95RoZHNk+Um7YI6MnJmeVpsDiO0zR1fh1luXezvp8IT092v3W/j0PMowjp6JahfRJ+u2dDBOOo6bTa3Vz6/qEPJkC5zda6uGsqRl5rE+Hbja+yodwU1qNyYz3LHhH8zkaf+qcmrilfj1yvM6dV1/b2Xoui8GixBxfLunqVhkJy5Pq+rikfXjL9nXU5oXfhWx66akaMtkwmrW53dcT2uXrWwp5zPG03S75dsW2vj+91Pz28lFoeVu9dXQRU5OSaR6ShKZ9mfJCmjukzpEzF7L7ELb5EUst++3BD2+Ufr0PmFXBvWSPA+onw9C4uT61vDVdkYPnfsNQhZHkQIR3dMpxPWIZwZfDb9YPQalen1sljDOsEivIl/f2DnqL7uLRyFE25zlsjhvVlxBBaLRxu1EKayy1bZf1Sri23itjemlVd1WOsAtQ3MqRmyfwB3DURI875eP2gppn4FvRVtkYB2pX0XjqePDIflBsPhUIw1ut996n7qNwUT+foVfKTsuevgeDhnpRby+2q18eixxHUPY3kZ/RsjGR7lGLlT/chSxXb964uAjI5pYECczWgeBBlCqO/hcezMAyjKLJihUm5cd6T3/JwEZ7eweWpTeMYzX0rwcAN9rZTl5gHEdLRLcP5pGpOvXt//42+0PcPZVl+/HBvFRy6eqzOp0jRl6RZ+Z5eZdvCc3CpQpDcvLtv+Gyb2zrPDvFTr4X0l1u2yvqlnDm3ushsyKqh6ulQBfRRkfXurmkYr7saIrkqNzUh7Uv6zKryIWdLch40tfm4oKwtt9p6/QkTfPe3LMt8WqYvsJY+uLVXK4+F737me6+5BjFzDu/h9jZTe7vEeDvxcr9GxouimGk8tTE75cZ1w9cdYJY/Wb13XREwkNPA4bYHmV2It7cwDMMwtGOFAH6Ek1bPFQFoa5iNM7r31T3C09y4PLXqcYRoRhpqNEuuIcuDCOnoluF8Uiu3n79+rGuoJx/CpmHXGhzsPaZmnYaiij6d/lxqHsoz5Hb/+KmLaabLLVtl/VLOmFsFOduyanBdy/wR1Y36qcj6dtckTFu+TG9BVWXXb1kOFJYlfV42lHKzGBW9YuK44uVJ6T+ScouiyGLK0KMa369gPVuSv1zqJZUj4DDKzXw7dR+qL0PbUG7tfOO73t1+sn7vqiKgJCcbixyVmxjHfOk+eDTb7Xa73c6OFcq3JsRzmQC6WO2tcmuIKk7Ys6auDxHS0S3D+aR5rpfXTBf7/f0T1kuG1Ow9pmadRFGaAZKadTvPwaVm5WbI7f7xU6eFTJdbtsr6pZwxtwpayu0WlX+UrmtXbtKN+qvI+nTXFIwN3XwYd1VuNm/ZXNJnZb3PlqxIL803tdEYHZVbv7Ml7ZovYxjXxdiTclNI6CGVm3w7v5XbXOOpzvjX7ZFyq4yfOcnllluiRuCq3OREfOHh45iDclO3roZSbmPNljxiFlE0Ndqgym2YCOnoluF80jxXNdT2tB5866zcdB6zbs89+RDSCZz289wcXGqeLempcmttlfVLOWNutbG9U63UPn9EuhGUW0drnc5qr9xs3jKUm5vxda24LoVbx7zvsLVcr/e9Q0kURRZThh7JKncpNtNr9ap+tqRXys3vKWplWXq06HF4I0RSTEsw8K2f2ZItWVLuJ8n+W5Fzk3JTFhzODnBHyiRJOqxzY0yqLHuZLTnWDiU0/9V+GHW2XUOWBxHS0S3D+UR8ro/XD4rHbN2pwsZjpjlUPAOb9rpDO8/FpWJ3NrdDST+zJS2513a88aRHyk0f2zvN4ddXAdob9VGR9e8u/02hhIV3p66I3RY42Jf0GdkgO5TUgUm/XHhf5Saixz0t/Jot2TaSoPeq6qeuyo25SpPDzu0S04OMb+WBKTeZb7RkdeGb48Ju9Xu3KQLXX1V9n2oOa++rv9GBWJ7ntl8FsFRuphXkOrXWPcLTk12eWn07sdeWj3J66ioGDH2IkI5uGc4nckVTco3j1tQ6e4zr6Rfac3WYcvGqm0uNXwXoa4cSu9Gqqih1apWp6N0P5Yy51cZ2632zLKuelhs5pjZgCZ2GcUqY8RXb8ar0G19lt4/OcTCV9PnYQHtLCqsDm5qA39m2H+XWb7+4ZzuUCOGMJWKbV7VfBXBQbs3dzV2we7RLjoTi541sO3p6VRSFxbeJ52Vs7cXJdR3frtiK7duHe/4ntn0mFnDb964rAjw5aWrfPtxws/JEDusfRFvWDsJKq34KN+V2pN212UG5PfqXuMuP79WDveqODGX0o+ZBhHR0y3A+Uekrkpo0dqFOzdpj5r3CBYpyORnEpaJXhZ4Im68CSKHVghV65aa/3D/lpo3t5gakoerRVgHaSqSXiqxfd/lu3KgaMT6AWFTE9/dP2mSCU0mfjfWi3GZlcyxCsI6WZVmSJKNnYybWdZsy2OPY1EMfrb9Hz4lvBreYrcMmZ3DplPzTb9UzQEXml7tg3huUm2goQjBqaZp6NHV2eqbovPfnY30wwaYe+qDczJ4ZPRu+2iN8aOHgbGz/9Fv1DF6Rje0u2MQMyk00FCEYNYy57WvCyoGZflxlHjb10AflZvbM6Nnw0OhUK9c1F3Cp7/7pt+oZuCIb312wSRmUm2goQjBqh7jODXaoNvXQB+Vm9szo2ZiTwaXwD9wFG8ug3ERDEYJRKw9tb0nYAdvUQx+Um9kzo2djTgaXwj9wF2wsg3ITDUUIRg1kgB2OTZ3tUG5mz4yejTkZXAr/wF2wsQzKTTQUIRi1oihABtiB2NRDH5Sb2TOjZ2NOBpfCP3AXbCyDchMNRQhGDcoNdjg29dAH5Wb2zOjZmJPBpfAP3AUby4JyYJA9HtI0DcMwDMPdbrfb7cIwjKIojuMkSZIkieM4YpBlGWkxs4mQ/6ZpGkURuTwMwziO8zxnTyMY+qGAyQE8BHwAeAj4APAQ8AHgIeADJsfDYZUbcUeSJFEU/fjxg/iCOCLLsjzPCx7kCHu58I88z+M4DmtEUZQkCesUAJABHgI+ADwEfAB4CPgA8BDwAVPk4YDKjTwhVZ/0AYhUNT+57jj1CHEuSTNNU/SjADqAh4APAA8BHwAeAj4APAR8wER5OKByy/OcjDCSrLP61Xwh1bVU7LI/ZVnGOoWMZgoDlyioAAV4CPgA8BDwAeAh4APAQ8AHTJSHQym3gp/rSSZ6WmY0z3My5ZRAGGQkKYf8VFThNJRMgAA8BHwAeAj4APAQ8AHgIeADpsvDQZQbUaJk2ihxBxkotMmo7lr2hCzLiK+JU2SPAEAJHgJ+ADwEfAB4CPgA8BDwAZPmobNyUz6YcJCdNmq/OI8mQiaJUqkqX05dhqnMBwvwEPAB4CHgA8BDwAeAh4APmD0PextzEzxCH4lkV3m+8Az0z6IokiShM0SFLTXpLajeJS5DyQRK8BDwA+Ah4APAQ8AHgIeAD5gNDweZLZnneRRF7ORO4QSdIKb/lueeyregc0zZZX/KlIHDBHgI+ADwEPAB4CHgA8BDwAdMmoddlFvBbKiiPCHPc3ZPFcEjrZku+FWDykHMQrWpS1Gjw0MBkwN4CPgA8BDwAeAh4APAQ8AHzJuHXda5kRFAQUSyMHukNX26nyYZgtTdRamGUSwPBOAh4APAQ8AHgIeADwAPAXscPb1q/Tf5s9WElGfPQzflRt1BVaYyu9QjdH6n/S1o+k6rBkt0qBwSwEPAAZtVGayGSBg8BHwAeAj4APAQcIK9cpP/bTj/EHjoptzyPE/TNI7jHz/+7ySgWG2aUzYrevjkvPLIb88CEcv1Vjo/WF0SIWs6v76oPlC7gEuHyc/jY7teBpq8MD/xD1SW3EMp0jE9lC5ZF58Id2cv1eZY96T2OVc+uJSIlECe52l6e7ZgbvL8v7QwSHk/Pv3cXjLZsiR3qLRuCtTvUPhksSmDYCCZVGNbLoNS5osBgyk3Jh7+IBWAroagy6Bnx8N/375i+j5//c789P1F0yd697tw3R93R6/+/sodYs7n0vEHTGhpD3fkZLlypMFOuFARBC3hPQ/v3mjrxBqbFf+LslLbrLhzNqu93OY3pGpRqteW662hptbVzuIFPfrPAx6KT7e6RL3sL4jiah1Jc1VuHvBQe/k4yi1N091uF0UXJ0Fw/MufYRgmSXK5IgWkIMVmud7meR7HX06Pg+DkIo7jOI45p1RnlUVxuWICx+UqCILnv8njjxvmLFowJYnCa8ERxdtmxdc0NC9stcNVQbqHYv7knlC8nzJZa5+o7y6fo9Ka6ie1zbn21tv10pidNE13u/OTxelNNdh9/iwIgtVlWZZFUVAn5HlOShdZPyrysIZQiuzHwQERm1UZBGUQlAMWP4+UWx0PIzrpIkkSQhWWMLPm4fcXjQD7/qIRXd9fPL366eJf8sPvvzLi7Y+7qmLmlBt7/r9vX3ko3thItl0vW8NdFd2kNjP5WQzJm1X3Sst7HmrrxAq1yuCqRE2lxh4euZN2IGiqRUG26q+tCaarnUVO9qbdRuahLOS36+Vchf0sMNCYm/fxsAe4Kbfq03I3p8fB8elNne/b18tgud6Wd2/I/+uRRHLa54j4JcuyPM+L4q6p87brZSXhijzP09vXi2BBko2aj9axdWSF+jrN3+LPY6LJS1smW3KtC9u6ZB19Yvxd8QocUmirbZWeMPfL0k8cUnw5WwSL1ySRS0a5sSPaPA/VM5Jpbw29Ch/xdMAqKFeb6r8NtuUyqBRdQH6Sj2yaP+tOmjIIyg1zfCMlVekx+VrdmT1D5iEhGPmVcuxwePj14lOlx/75+6enn97+U/8g/MmeqfpTPn90tFQ6FE2426yC5Xq9YoPfarVihkp6q6SmxUPJc8RlTD2hrbzoOVZV0qQh88tCuWndwqTGJ9OrI0floVWJMks5CL1Hg26JmrxirXRf5zateNgNzrMlkyQJw/OTICDaLYqiv84WwfLNtmyUW1FtunJxEgQn580TZlmWXz4XB5uWb26zLEmSz6cLmmbz6QNVuFKGfq471Jvyx3aByTNn2L+N2dZHJW2ybj4xnWDV16fLIn/YRrkZslJfzhY5gouTIFic3RVFySi3gtn8hy1ppHCyCZPx6yzLhC8n4lMwLthU+oob49qWS0bIbdflai0dWTHDdHUiwsTLzaoMluW2TpAZ5FBdy990yNmSAg8JZ4TuvcPh4e+/0pG07y+YUTVRmLUqt/L7i6dXL/54nFxbQaM3hLOE+SHL9bae9EZahRtWufXWYp4WD/kqgfpVM7TG/V39o1fZ6ym6KDf9GcJQMBN9+2wsjclDO05AuXkFpWxTijfdJUpMKx52g/PekmSEMYo+n9JVRouzWyJn6/4bok2Tv86Og+DkfEc3b4njL68XweL1bVaDW610fHpTzxmt3aEOLKqjxiVkY4Gd9ddNuVWPpX8kU7IOPtFHcLvYLs9vbM257gabVRAsl8wcfWVdVPMwqgeBg8XZF9Ktwk91f/5b/bVEhocxKZ8MD9MkSWhXSijyELBAI5A2zfCXrJqUR5br5s8VMwrHrHupBRuv3JTXCrcYTLmVAg9r5tDuPYKCWTA9Zx7+8/dPzAxJbgmcuKRNOcjGSDXhTx8gjE6o/gzEQLZcb6v/VY1CeTKlNsK5YTI85GsKtVwzKrflcu7DbWVZ6pSbqVY01+HygpP+yMdgLB5ajh1CuXkFy9mSrcdlTCYedkWXrwJk2e1ZNTxG2szNcAcXFhaLRRCcnFdO2e12u/OTIDi5iCg+nx4Hx7/8udvt/vzlmIrAxheaPiTDTENrvfAI0NZRyr/b5ysy6yMaOaZNVuMT4fLWu1sNuBnWpbUtWdMot9Z1csxs45vT42oXEtqtQsEuntwxCOvxcVq22Z98XVPkN9hJkqugElTrJaesdEeCgDOFcqPp88pNea1wiyGVmzDrXejeU542Ux7++/YVq9D+ffuqUnFfLz7J4k0ehWvWvz29Onr1yTvlVvK1m1pACH11zcT15VIzSbJJc69KayI85KoDPvLbKreqW2/u2s3cY6oYstXW1EIVPOBsyXI8HhqfQ7GLC1PgzL8CA0JYtMZOfZRFmv0nAcrJxMPu6PIl7nKzCoJn57U7wpvTRRA8v5Q+Qnf3ZhEszv6iw4vM8jiC85N6NmUYRVHy19lC2l1KWXxUbX1xV6qxA7ukWPZSbjbLKvi/HX2iSd5mwK1Nm7kusXNxTJreUtlGWCTOOd6ul8Hy9S03zG1AVO8ha3xkQMZGVFBkcqOlchOO0ARtlJt87SMqN4I0TSl/1DysK4mZ8lCQbUSGMftJSmNoCuXGwr91biJ0YYlblMV0ndG1b/oesv0rLb95KNYU6iZzNRvSNFvSoj9w8nBsD5joaJ7la7cYwg0j8BCzJScI8/RIVtcZzjQMxPkdD/dClzG3crMKgucXjR49PwmCZ/8Rt8XcrIJg+eb/6ZI+otNYXVsPwRFf5PklF0P0EaWtrT9ELHKCqmLpYYcSc0OB/9PRJ+q7tzvSogptC6ltdZD6ejKZ9s0yCBZkE5yq1Inbs27Xy2D55o5bWrrjEdb9KzUPfd8HwkcIsxapvrKcLalQVqrZknQNGztbUr5WyMzAY25lWeZ5zvbPKXhYnzxHHkqyrZSUm7RuzazcmPVynsIowQTlVm7XS9WOvyz27W70noetNYXTDiXVRJKx+2cHhJtyU9fUSp8P2889Hg+xQ8n0IGiz1pG00rjtJAvv4+G+6DTmRqLms/+QiaQ3p8dBcPIbP4BIYwZxSpbdkhVuSY00TbPb14ug+hJXURR8CDEFLlVbX1jdNWJI1/aeipssmjfM3LC7RJueSZ2so090SweNgUzzpIac2+xQwsdg7nru8uoPUt5on0r85WyxeF3N3WWqrpqHWZqmZNZyw8MahIf65wX0EPeTpBMm+c1Cyo24Q0m5qXYoYfcsWW9F5bZe1upLSrDlWrLJ5LBjbmVZijzUTKiYHQ/ZLwEw+Ofvn5jjXy8+CZ90Myi3rxefjvwecBPXDanD3UbxnUp2hxKxY62fSstLHto8HlclaupK6Zz5DrwpGjn8ti6qXV5Y6HzONz163SmHxQg8lAkhSTEoN69gnhtpuKr1HAov42EP6KLcivrTbTVOLqIoDMM4jv/7vJn0cMk85N2bZRCsLvMGtRfYdMQK8FL2lDDBQohA0tERoJoC0rJliPqh2hYkN9DtRGLnE41L2wWw9kn1ORfqCe3b1CzfZy9X3f3kIqq+7cZczVKIsC5X8NAEr0qsj9iuFd9wE3aD5Dbul49sxGmW4vTLlXg75VcBqmvZc5bletjZknTHKnaL4VCaDT9PHrKL02qrx9Y0X+IWLqnV3e+/6j/b7Qc0e4rowp1RuYnxq4cWo788NNWJ3EniWJDoG+U5s2tsO7YH1DW1Ze08gPdG5eHgTwf0AmFUzUm5yZcr4W887AMdlRvJaMZ/NiGqd8mkpykvtH9IH1sqgDcAD2cNaZ2brwAPAR8AHgI+ADwEXGE5W9I8kVLAvHm4l3Jjt9Skw5HsRFKUK6CUejXkg52TBQ/ni/6VG3gI+ADwEPAB4CHgA4qioGKMUkK5BM412RnzsNM6txpFUbAfFKcTScf6rDjgP4YoLeDhHDHsmBt4CPgA8BDwAeAh4APAQ0vsq9yInI2iiOzBQiB/8w44ZBT11OGBOjnAQ8AG4CHgA8BDwAeAh4APAA87YC/lVjJfsiMeIdtoRlE0XY8A/YIWG7aHo/fhafAQMAM8BHwAeAj4APAQ8AHgYTfsq9xKZvMW+gGEOI6nOwoJ9AUyz5h+5ZDt4RhiYjF4CCgBHgI+ADwEfAB4CPgA8HAfdPoSt3SE3byF7NwyxTV/QI8o6u9jkI9pkK4OSoxelkHLR8BDQAB4CPgA8BDwAeAh4APAwz3RXbmxz0yGO+M4juPYvOEmcAgomG/Sk6JCOzn6Gp4GD4FWgIeADwAPAR8AHgI+ADzcH/8DOLyxnsEHz70AAAAASUVORK5CYII=" alt="" width="688" height="34" />

 #include <map>
#include <set>
#include <stack>
#include <queue>
#include <cmath>
#include <ctime>
#include <vector>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
#define eps 1e-15
#define MAXN 105
#define INF 1000000007
#define MAX(a,b) (a > b ? a : b)
#define MIN(a,b) (a < b ? a : b)
#define mem(a) memset(a,0,sizeof(a)) bool G[MAXN][MAXN],vis[MAXN];
int Left[MAXN],N,M,T,a[MAXN],b[MAXN]; bool DFS(int u)
{
for(int v=;v<=N;v++) if(G[u][v] && !vis[v])
{
vis[v] = true;
if(!Left[v] || DFS(Left[v]))
{
Left[v] = u;
return true;
}
}
return false;
} int main()
{
while(~scanf("%d", &N))
{
mem(G); mem(Left);
int x,ans = ;
for(int i=;i<=N;i++) for(int j=;j<=N;j++)
{
scanf("%d", &x);
if(x)G[i][j] = true;
}
for(int i=;i<=N;i++)//求最大匹配
{
mem(vis);
if(DFS(i)) ans ++;
}
if(ans < N){printf("-1\n");continue;}//小于N无解
int tot = ,j;
for(int i=;i<=N;i++)
{
for(j=;j<=N && Left[j]!=i ;j++);
if(i != j)//交换第i列和第j列
{
a[tot] = i; b[tot] = j; tot ++;//记录结果
int t = Left[i]; Left[i] = Left[j]; Left[j] = t;
}
}
printf("%d\n",tot);
for(int i=;i<tot;i++) printf("C %d %d\n", a[i],b[i]);
}
return ;
}
上一篇:C#中各种计时器 Stopwatch、TimeSpan


下一篇:解决adb问题的方法