POJ 1486 最大匹配

POJ 1486

题意

平面上给出几张幻片灯.且包含一些数字.找到可以确定唯一数字对应的幻片灯(矩形内),

思路

  1. 在dfs求出每个数字所匹配的幻灯片后.还要确定该匹配边的唯一性.即如果去掉该边.重新匹配且最大匹配数未变.则说明该匹配边不是唯一的.
  2. 输出能够确定的数字的幻灯片.所有幻灯片都无法确定则输出none
  • 构造一个struct {} edge[];来存所有第一次dfs的所有匹配边.通过它来判断每条边是否有效
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <iostream>
#include <cstring>

using namespace std;
const int maxn = 35;

class solution {
public:
    int n,m;
    bool g[maxn][maxn],vis[maxn];
    int left[maxn]; //数字i匹配的幻片灯

    void init(int n) {
        this->n = n;
        memset(g,0,sizeof g);
        memset(left,-1,sizeof left);
    }

    bool match(int u) { // dfs求left匹配数组
        for (int v=1; v<=n; ++v) // 遍历所有数字
            if (g[u][v] && !vis[v]) {
                vis[v] = 1;
                if (left[v]==-1 || match(left[v])) {
                    left[v] = u;
                    return 1;
                }
            }
        return 0;
    }
    int solve() {
        int ans=0; // 匹配边的数量
        for (int i=1; i<=n; ++i) {
            memset(vis,0,sizeof vis);
            if (match(i)) ++ans;
        }
        return ans;
    }
};

int xmin[maxn],ymin[maxn],xmax[maxn],ymax[maxn];
struct {
    int num;
    bool use;
} edge[maxn]; // 边的编号是幻灯片的编号

int main() {
    freopen("1.in","r",stdin);
    solution ss;
    int n,kase=0;
    while (scanf("%d",&n) && n) {
        ss.init(n);
        memset(edge,0,sizeof edge);
        for (int i=1; i<=n; ++i) scanf("%d%d%d%d",&xmin[i],&xmax[i],&ymin[i],&ymax[i]);
        for (int i=1; i<=n; ++i) { //读取n个数字坐标
            int x,y; scanf("%d%d",&x,&y);
            for (int j=1; j<=n; ++j) //判断数字是否在幻灯片内,在就标记幻灯片到该数字的边
                if (xmin[j]<=x && x<=xmax[j] && ymin[j]<=y && y<=ymax[j])
                    ss.g[j][i] = 1;
        }
        ss.solve();
        int edge_num = n; //假设n条一对一的有效匹配
        for (int i=1; i<=n; ++i) { // 扫描所有数字匹配的边.把边存起来存起来,
            edge[ss.left[i]].num = i;
            edge[ss.left[i]].use = 1;
        }
        for (int i=1; i<=n; ++i) { //遍历所有边,判断边是否有效
            int j = edge[i].num;
            ss.g[i][j] = 0; //假设去掉这条边
            memset(ss.left,-1,sizeof ss.left);
            int num = ss.solve();
            if (num == n) {
                edge[i].use = 0; //该匹配边可以被替换,则不是一对一的数字
                --edge_num;
            }
            ss.g[i][j] = 1;//还原
        }
        printf("Heap %d\n",++kase);
        if (edge_num == 0) printf("none\n");
        else {
            for (int i=1; i<=n; ++i)
                if (edge[i].use)
                    printf("(%c,%d) ",i-1+'A',edge[i].num);
            printf("\n");
        }
        printf("\n");
    }
    return 0;
}
算法

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！