题意

给你n个幻灯片，每个幻灯片有个数字编号1~n，现在给每个幻灯片用A~Z进行编号，在该幻灯片范围内的数字都可能是该幻灯片的数字编号。问有多少个幻灯片的数字和字母确定的。

思路

确定幻灯片的数字就是求完美匹配也就是最大匹配，而题目要求的边就是

匹配的关键边，也叫必须边，即任意一个最大匹配一定要包含这条边。

关键边求法： 先求一遍最大匹配，然后枚举删去匹配边，看之后的最大匹配是否减小，如果减小则该边是匹配关键边。 这让我想起了寻找关键割边：如果一个割边增加流量后整个最大流增加则该割边是关键割边。呵呵，是不是很像？算法的魅力之一就在于举一反三吧^_^~

代码

 

#include #include #include #include #include #include #include #define MID(x,y) ((x+y)/2)#define mem(a,b) memset(a,b,sizeof(a))using namespace std;const int MAXV = 55;                   //N1+N2vector  adj[MAXV];struct MaximumMatchingOfBipartiteGraph{    int vn;    void init(int n){                   //二分图两点集点的个数        vn = n;        for (int i = 0; i <= vn; i ++)     adj[i].clear();    }    void add_uedge(int u, int v){		adj[u].push_back(v);		adj[v].push_back(u);    }    bool vis[MAXV];    int mat[MAXV];                      //记录已匹配点的对应点    bool cross_path(int u){        for (int i = 0; i < (int)adj[u].size(); i ++){            int v = adj[u][i];            if (!vis[v]){                vis[v] = true;                if (mat[v] == 0 || cross_path(mat[v])){                    mat[v] = u;                    mat[u] = v;                    return true;                }            }        }        return false;    }    int hungary(){        mem(mat, 0);        int match_num = 0;        for (int i = 1; i <= vn; i ++){            mem(vis, 0);            if (!mat[i] && cross_path(i)){                match_num ++;            }        }        return match_num;    }}match;struct xy{    int x1, x2, y1, y2;    int x, y;}a[MAXV];bool del[MAXV][MAXV];void build(int n){    match.init(n+n);    for (int i = 1; i <= n; i ++){        for (int j = n+1; j <= n+n; j ++){            if (!del[i][j] && a[j].x >= a[i].x1 && a[j].x <= a[i].x2 && a[j].y >= a[i].y1 && a[j].y <= a[i].y2){                match.add_uedge(i, j);            }        }    }}map  key_match;int main(){	//freopen("test.in", "r", stdin);	//freopen("test.out", "w", stdout);	int n;	int t = 1;	while(scanf("%d", &n), n){        for (int i = 1; i <= n; i ++){            scanf("%d %d %d %d", &a[i].x1, &a[i].x2, &a[i].y1, &a[i].y2);        }        for (int i = 1; i <= n; i ++){            scanf("%d %d", &a[i+n].x, &a[i+n].y);        }        mem(del, false);        build(n);        int max_match = match.hungary();        key_match.clear();        for (int i = 1; i <= n; i ++){            key_match.insert(make_pair(i+64, match.mat[i]-n));        }        map  :: iterator it;        for (it = key_match.begin(); it != key_match.end(); it ++){            del[it->first - 64][it->second+n] = true;            build(n);            del[it->first - 64][it->second+n] = false;            int tmp_match = match.hungary();            if (tmp_match == max_match){                it->second = -1;            }        }        printf("Heap %d\n", t ++);        bool ok = 0;        for (it = key_match.begin(); it != key_match.end(); it ++){            if (it->second == -1)   continue;            ok = 1;            printf("(%c,%d) ", it->first, it->second);        }        if (ok){            puts("\n");        }        else{            puts("none\n");        }	}	return 0;}