最小覆盖问题
Ａ公司和Ｂ公司举行一个秘密会议，A公司的M为代表（编号为1，2，3……M）和B公司的N位代表（编号为1，2，3……N）参加了秘密会议，会议又2公司代表间的K组秘密会谈组成，每次秘密会谈双方各派一位代表参加，每位参加会议的代表都至少参加了一组秘密会谈，为了确保会议内容的机密，要为参加秘密会谈的代表建立专用加密通道。每一条专用通道的费用是相同的。由于建立专用加密通道费用昂贵，公司总裁决定建立最少的专用加密通道，使的每位代表至少有一条专用加密通道，工程师接到K组参加秘密会谈人员的编号后，如何用尽量少的花费建立满足公司总裁要求的加密通道。
编程任务：
对于给定的K组参加秘密会谈人员的位置，编程计算满足公司总裁要求的最少加密通道数
数据输入
又文件input.txt给出输入数据，第1行有3个整数m,n,k，表示A公司有m位代表，B公司有n位代表参加了秘密会议，举行K组秘密会谈，接下来的K行，每行又2个正整数x和y组成，表示秘密会谈在A公司的代表x和B公司的代表y之间举行。
结果输出
将编程计算出的最少加密通道数输出到文件 output.txt
输入文件示例 输出文件示例
iput.txt output.txt
2 3 4 3
1 1
2 1
3 1
3 2
谁帮我看下这道题是用求什么的？题目理解的不是很清楚？给个思路
问题点数：50、回复次数：13Top
1 楼air128289（）回复于 2006-06-08 18:02:50 得分 0
帮我看看Top
2 楼air128289（）回复于 2006-06-11 23:35:42 得分 0
有没有人懂的啊?Top
3 楼yyfhz（火山）回复于 2006-08-01 15:45:35 得分 0
是不是这个意思啊，
A公司有2个人，B公司有3个人，一共要开43次会。
1号会议由A1和B1进行
2号会议由A2和B1进行
3号会议由A3和B1进行
4号会议由A3和B2进行
...
以现在来看，如果为A1,A2,A3建立通道的话，则一共需要建立3个通道，而如果为B1和A3来建立加密通道的话，只需要2个通道，但是所有的会议同样可以召开。Top
4 楼LeeMaRS（小菜虎，仍需努力）回复于 2006-08-01 18:46:04 得分 0
题目是下面这个意思 :
有两个公司, A公司有m个人, B公司有n个人, 现在要开k个会, 然后告诉你每个会是A公司的哪个人和B公司的哪个人开, 要求这两个人至少要有一个人有加密通道. 问最少要建多少个加密通道.
做法很简单, 按题目给的K个会议建一个二分图, 左边是A公司的人, 右边是B公司的人, ai和bj要开会, 就连一条边(ai,bj). 然后就是要求二分图上的最小点覆盖数(最小点覆盖 - 选一些边, 使得图中的每一个点至少被一条边覆盖).
设此二分图的最大匹配数是M, 则答案是m + n - M.
上面的变量名要区分大小写, 恩.Top
5 楼Ichigo（）回复于 2006-08-01 20:51:00 得分 0
越看越糊涂.
理解1: 会谈地点唯一, 代表住所每人一个, 现需建立住所到会谈地的代表个人专用秘密通道. (问题简单了, 每人一条足亦, 且每人都参加过会谈, 则通道数=m+n)
理解2: K组会谈位于不同的K个会议室, 需建立住所到会议室的专用通道. (问题似乎也不难, 通道数=2K, 因为每组会谈有两个代表, 而通道必需代表专用)
理解3: 无专门会谈地, 会谈在代表住所进行, 则每进行一次会谈, 就会在某两个代表间联接一个通道, 共K组会谈, 则通道数为K.
以上理解均假设每组会谈仅包含一次会谈涉及A B公司各一个代表(我认为这是题目讲的最不清楚的地方了).
不管是哪种理解, 我都看不懂输入文件的意思, 似乎人数跟编号对不起来. 也不论哪种理解, 我都得不到输出结果3.
Top
6 楼LeeMaRS（小菜虎，仍需努力）回复于 2006-08-01 21:48:19 得分 0
1 - 1
2 - 1
3 - 1
3 - 2
最大匹配是1 - 1
3 - 2
所以需要3 + 2 - 2 = 3个通道.Top
7 楼mmmcd（超超）回复于 2006-08-17 12:59:48 得分 0
每位代表至少有一条专用加密通道；
某两位代表可共用一条专用加密通道
把最多的可共用数找出来，再用总人数去减。Top
8 楼bigc2000（公元2005年4月9日）回复于 2006-08-25 11:26:09 得分 0
晕啊，这好像就是
通道数 = max{M，N}
是不是要求，同时开，没有这个要求，就是这个了Top
9 楼beesharp（猪三）回复于 2006-09-08 11:21:49 得分 0
二分图的最小点覆盖..求最大匹配就可以了吧Top
10 楼zzwu（未名）回复于 2006-09-13 16:58:01 得分 0
一共开43次会? 还是开4次会?Top
11 楼zzwu（未名）回复于 2006-09-13 17:10:27 得分 0
问题确实不清楚,
例如,题目要求"每位参加会议的代表都至少参加了一组秘密会谈"
但
2 3 4
1 1
2 1
3 1
3 2
中,第一行的"2 3 4"说明Ａ公司是2人,Ｂ公司有3人
而接着的
1 1
2 1
3 1
3 2
则说明Ａ公司有板有眼人(1,2,3),Ｂ公司则是2人(1,2)
这不是矛盾吗?
Top
12 楼zzwu（未名）回复于 2006-09-13 17:11:43 得分 0
问题确实不清楚,
例如,题目要求"每位参加会议的代表都至少参加了一组秘密会谈"
但
2 3 4
1 1
2 1
3 1
3 2
中,第一行的"2 3 4"说明Ａ公司是2人,Ｂ公司有3人
而接着的
1 1
2 1
3 1
3 2
则说明Ａ公司有3人(1,2,3),Ｂ公司只有2人(1,2)
这不是矛盾吗?
Top
13 楼Riemann（）回复于 2006-09-17 12:42:07 得分 0
to LeeMaRS(小菜虎，仍需努力)：
2个通道足矣，最小覆盖数应为3。Top
