poj1486（二分图删边匹配） - c++编程基础

题意：给ｎ(n<=26)张幻灯片，每张上面都有一个数字。给出所有幻灯片的位置和数字的位置，问哪些幻灯片上的数字可以确定。

解法：首先，如果给的合法的话，匈牙利算出来的一定是完全匹配的(也就是说，第一遍二分匹配算出来的一定是完全匹配)。然后再尝试删掉每一条完全匹配中的边，如果删掉后不能完全匹配，则说明这条边是必须的，所以就确定了这个匹配并输出。如果算出的完全匹配中没有一个匹配是必须的，就输出none好了。

代码：

/******************************************************
* author:xiefubao
*******************************************************/
#pragma comment(linker, "/STACK:102400000,102400000")
#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
           #include 
           
             #include 
            
              #include 
             
               //freopen ("in.txt" , "r" , stdin); using namespace std; #define eps 1e-8 const double pi=acos(-1.0); typedef long long LL; const int Max=10100; const int INF=1000000007; int n; struct rec { int minx,miny,maxx,maxy; } recs[30]; bool num[30][30]; bool used[30]; int match[30]; int match2[30]; struct point { int x,y; } points[30]; bool OK(const rec& re,const point& p) { return (p.x>=re.minx&&p.x<=re.maxx&&p.y>=re.miny&&p.y<=re.maxy); } bool dfs(int k) { for(int i=0;i