最大匹配必须边

poj1486

题意：

给出一些矩形的坐标和一些点的坐标，若点在矩形内，则该点和该矩形匹配。

问哪些匹配边是可以唯一确定的，可以先求出最大匹配，然后每次删除一条匹配边，

然后再求最大匹配，如果匹配个数不变，那么该边不是必须边，否则就是必须边

 1 #include <stdio.h>
 2 #include <string.h>
 3 const int N = 1000;
 4 struct node
 5 {
 6     int xMin,xMax,yMin,yMax;
 7 }slide[N];
 8 int Map[N][N];
 9 bool vis[N];
10 int cy[N];
11 int cx[N];
12 int n;
13 int path[N];
14 bool dfs(int u)
15 {
16     for(int i=0; i<n; ++i)
17     {
18         if(!vis[i] && Map[u][i])
19         {
20             vis[i] = true;
21             if(cy[i]==-1 || dfs(cy[i]))
22             {
23                 cy[i] = u;
24                 cx[u] = i;
25                 return true;
26             }
27         }
28     }
29     return false;
30 }
31 int MaxMatch()
32 {
33     int cnt = 0;
34     memset(cy, -1, sizeof(cy));
35     memset(cx, -1, sizeof(cx));
36     for(int i=0; i<n; ++i)
37     {
38         if(cx[i]==-1)
39         {
40             memset(vis, 0, sizeof(vis));
41             cnt += dfs(i);
42         }
43     }
44     return cnt;
45 }
46 int main()
47 {
48     
49     int i,j,x,y;
50     int tCase = 1;
51     while(true)
52     {
53         scanf("%d",&n);
54         if(n == 0)
55             break;
56         for(i=0; i<n; ++i)        
57             scanf("%d%d%d%d",&slide[i].xMin,&slide[i].xMax,
58                             &slide[i].yMin,&slide[i].yMax);
59         memset(Map, 0, sizeof(Map));
60         for(i=0; i<n; ++i)
61         {
62             scanf("%d%d",&x,&y);
63             for(j=0; j<n; ++j)
64             {
65                 if(x>=slide[j].xMin && x<=slide[j].xMax 
66                     &&y>=slide[j].yMin && y<=slide[j].yMax)
67                     Map[j][i] = 1;
68             }
69         }
70         printf("Heap %d
",tCase++);
71         int ans = MaxMatch();//求出最大匹配
72         bool flag = false;
73         for(i=0; i<n; ++i)//记录X集合中的i与Y集合中的那些点匹配
74             path[i] = cx[i];
75     
76         for(i=0; i<n; ++i)
77         {
78             Map[i][path[i]] = 0;//删除匹配边
79             if(ans == MaxMatch())
80                 continue;
81             //如果，匹配的个数减少，那么该匹配边是必须边
82             if(flag)
83                 printf(" ");
84             flag = true;
85             printf("(%c,%d)",'A'+i,path[i]+1);
86             Map[i][path[i]] =1;
87         }
88         
89         if(!flag)
90             printf("none");
91         puts("");
92         puts("");
93     
94     }
95     return 0;
96 }