Asteroids

  1 /*
  2 题意:给定网格中的一些点，每次可以覆盖一行（和）一列（行列都覆盖）
  3 求最小覆盖
  4 解：看作二分图，求最大匹配数，最大匹配时，满足最小覆盖
  5 */
  6 
  7 #include <cstdio>
  8 #include <cstring>
  9 
 10 using namespace std;
 11 
 12 const int max_N = 500+5;
 13 const int max_K = 1e4+10;
 14 // e存储边信息
 15 // pred？存储临接信息
 16 int n,k,e[max_N][max_N],pred[max_N],queue[250010];
 17 // cx，cy，分别表示x集合的匹配和y集合的匹配信息
 18 int cx[max_N],cy[max_N];
 19 
 20 // 求最大匹配数，x集合与y集合在满足题目条件下的的最大匹配数
 21 // 即为最小覆盖数
 22 int maxmatch()
 23 {
 24     // y记录之后广搜中，从队列中取出的数
 25     // 由于x已经匹配，用y记录这一x可以匹配的y
 26     int y;
 27     int cur,tail,res=0;
 28     // 初始化为-1
 29     memset(cx,0xff,sizeof(cx));
 30     memset(cy,0xff,sizeof(cy));
 31     //printf("%d\n",cx[1]);
 32 
 33     for(int i=1;i<=n;++i)
 34     {
 35         // 找到x集合中每个未覆盖点i进行一次交错轨
 36         if(cx[i]!=-1)
 37         {
 38             continue;
 39         }
 40 
 41         //初始化pred数组为-2
 42         for(int j=1;j<=n;++j)
 43         {
 44             pred[j]=-2;
 45         }
 46         // 队列初始化
 47         cur=0;
 48         tail=0;
 49         // x已经匹配，将所有与x临接的顶点加入队列进行寻找
 50         for(int j=1;j<=n;++j)
 51         {
 52             if(e[i][j])
 53             {
 54                 // 用pred【j】==-1，表示已遍历到的临接顶点
 55                 pred[j]=-1;
 56                 queue[tail]=j;
 57                 ++tail;
 58             }
 59         }
 60 
 61         // BFS
 62         while(cur<tail)
 63         {
 64             // 从队列中取出一个数
 65             y=queue[cur];
 66             // 找到了一个未匹配的点，则找到了一条交错轨
 67             if(cy[y]==-1)
 68             {
 69                 break;
 70             }
 71             // 没找到交错轨，继续寻找队列中下一节点
 72             ++cur;
 73             // 由于当前点已经匹配给了cy[y]
 74             // 从cy[y]出发，将其邻接点加入队列
 75             for(int j=1;j<=n;++j)
 76             {
 77                 if(pred[j]==-2 && e[ cy[y] ][j])
 78                 {
 79                     // 将与y匹配的x所在行中的所有点加入队列
 80                     // 并用pred记录x所对应的y值
 81                     pred[j]=y;
 82                     queue[tail]=j;
 83                     ++tail;
 84                 }
 85             }
 86         }
 87         // 如果没有找到交错轨，则不能得到更大的匹配数
 88         // 跳过进行下次寻找
 89         if(cur==tail)
 90         {
 91             continue;
 92         }
 93         
 94         // 当找到了交错轨时，即找到了一个未匹配的点(cy[y]==-1)时
 95         // 更改交错轨上的匹配状态
 96         while(pred[y]>-1)
 97         {
 98             // 之前y匹配的那个x匹配的数改成当前y
 99             cx[ cy[ pred[y] ] ] = y;
100             // 现在的y匹配前一个y匹配的那个x，空出现在的y待匹配
101             cy[y] = cy[ pred[y] ];
102             // y 更新为可行交错轨上前一个y
103             y=pred[y];
104         }
105         
106         // cx[i]是空闲未匹配的，最早的cy[y]已被空出
107         cy[y]=i;
108         cx[i]=y;
109         // 匹配成功，匹配数+1
110         ++res;
111     }
112 
113     // 二分图的最小顶点覆盖数=最大匹配数
114     // 返回最小顶点覆盖数，即为所求结果
115     return res;
116 }
117 
118 int main()
119 {
120     int x,y;
121     while(scanf("%d %d",&n,&k)!=EOF)
122     {
123         memset(e,0,sizeof(e));
124         for(int i=1;i<=k;++i)
125         {
126             scanf("%d %d",&x,&y);
127             e[x][y]=1;
128         }
129         printf("%d\n",maxmatch());
130     }
131     return 0;
132 }