题意

给你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+N2

vector  adj[MAXV];

struct MaximumMatchingOfBipartiteGraph{

    int vn;

    void init(int n){                   //二分图两点集点的个数

        vn = n;

        for (int i = 0; i = a[i].x1 && a[j].x = a[i].y1 && a[j].y  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  :: 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;

}