POJ 1486 Sorting Slides (二分图关键匹配边)

题意

给你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;
}
上一篇:commonJS — 通用方法(for COM)


下一篇:Java程序员必须掌握的常用Linux命令。