POJ 1486 Sorting Slides

http://poj.org/problem?id=1486

题意：给n个矩形的4个边界的坐标（左上和右下），分别是：xmin、xmax、ymin、ymax。又给出四个数字的坐标。每个数字只能属于一个矩形。求出每个数字的从属关系。

题解：二分图最大匹配问题：数字和矩形的匹配。要求出每一条必须边。先求出最大匹配ans，然后删除每一条边，再进行匹配，看最大匹配是否等于ans：如果相等，则这条边不是必须边；如果小于ans，则这条边是必须边。

注意点：删除边之后要恢复这条边；输出格式……

  1 #include <iostream>
  2 #include <cstring>
  3 #include <cstdio>
  4 #include <cstdlib>
  5 #include <cmath>
  6 #include <string>
  7 #include <vector>
  8 #include <list>
  9 #include <map>
 10 #include <queue>
 11 #include <stack>
 12 #include <bitset>
 13 #include <algorithm>
 14 #include <numeric>
 15 #include <functional>
 16 #include <set>
 17 #include <fstream>
 18 
 19 using namespace std;
 20 
 21 const int maxn=110;
 22 int V;
 23 int G[maxn][maxn];
 24 int match[maxn];
 25 int used[maxn];
 26 int n;
 27 struct cos{
 28     int xmin,xmax,ymin,ymax;
 29 }s[maxn];
 30 struct numb{
 31     int x,y;
 32 }num[maxn];
 33 
 34 bool dfs(int v)
 35 {
 36     for (int i=0; i<n; i++) {
 37         if (!used[i]&&G[v][i]) {
 38             used[i]=1;
 39             if (match[i]==-1||dfs(match[i])) {
 40                 match[i]=v;
 41                 return true;
 42             }
 43         }
 44     }
 45     return false;
 46 }
 47 
 48 int bipartite_matching()
 49 {
 50     int res=0;
 51     memset(match, -1, sizeof(match));
 52     for (int v=0; v<V; v++) {
 53        // if (match[v]<0) {
 54             memset(used, 0, sizeof(used));
 55             if (dfs(v)) {
 56                 res++;
 57             }
 58         //}
 59     }
 60     return res;
 61 }
 62 int main()
 63 {
 64     //freopen("/Users/apple/Desktop/POJ 1486/POJ 1486/in", "r", stdin);
 65     // freopen("/Users/apple/Desktop/POJ 1486/POJ 1486/out", "w", stdout);
 66     int mycase=0;
 67     while ((scanf("%d",&n))!=EOF&&n!=0) {
 68         V=n;
 69         mycase++;
 70         memset(G, 0, sizeof(G));
 71         for (int i=0; i<n; i++) {
 72             scanf("%d%d%d%d",&s[i].xmin,&s[i].xmax,&s[i].ymin,&s[i].ymax);
 73         }
 74         for (int i=0; i<n; i++) {
 75             scanf("%d%d",&num[i].x,&num[i].y);
 76         }
 77         for (int i=0; i<n; i++) {
 78             for (int j=0; j<n; j++) {
 79                 if ((num[j].x>=s[i].xmin)&&(num[j].x<=s[i].xmax)&&(num[j].y>=s[i].ymin)&&(num[j].y<=s[i].ymax)) {
 80                     G[i][j]=1;
 81                 }
 82             }
 83         }
 84         printf("Heap %d
",mycase);
 85         int ans=bipartite_matching();
 86         bool flag=false;
 87         for (int i=0; i<n; i++) {
 88             for (int j=0; j<n; j++) {
 89                 if (G[i][j]==0) {
 90                     continue;
 91                 }
 92                 G[i][j]=0;
 93                 if (bipartite_matching()<ans) {
 94                     flag=true;
 95                     printf("(%c,%d) ",'A'+i,j+1);
 96                 }
 97                 G[i][j]=1;
 98             }
 99         }
100         if (flag==0) {
101             printf("none

");
102         }
103         else printf("

");
104     }
105     return 0;
106 }