给一个N*N的矩阵，有些格子有障碍，要求我们消除这些障碍，问每次消除一行或一列的障碍，

最少要几次。

_____________________________________________________________________

以行作为一部顶点，列作为一部分顶点。交叉点有障碍则连边。

但选择一个顶点时，则这一行或列上的障碍消除，即与这个顶点相连的边消除，所以这个题本质是求二分图最小点覆盖。

匈牙利算法。

_____________________________________________________________________

 

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5  6 using namespace std; 7 const int maxn=505; 8 int n,k; 9 struct edge10 {11     int u,v,next;12 }e[maxn*maxn];13 int head[maxn],js;14 bool vis[maxn];15 int link[maxn];16 void addage(int u,int v)17 {18     e[++js].u=u;e[js].v=v;19     e[js].next=head[u];head[u]=js;20 }21 bool dfs(int u)22 {23     for(int i=head[u];i;i=e[i].next)24     {25         int v=e[i].v;26         if(!vis[v])27         {28             vis[v]=1;29             if(link[v]==0 || dfs(link[v]))30             {31                 link[v]=u;32                 return 1;33             }34         }35     }36     return 0;37 }38 int main()39 {40     scanf("%d%d",&n,&k);41     for(int l,r,i=0;i