先上题目吧
What’s In A Name?
| **Time Limit:**
1000MS
|
|
**Memory Limit:** 10000K
|
| **Total
Submissions:** 1614
|
|
**Accepted:**
547
|
Description
The FBI is conducting a surveillance of a known
criminal hideout which serves as a communication center for a number of
men and women of nefarious intent. Using sophisticated decryption
software and good old fashion wiretaps, they are able to decode any
e-mail messages leaving the site. However, before any arrest warrants
can be served, they must match actual names with the user ID’s on the
messages. While these criminals are evil, they’re not stupid, so they
use random strings of letters for
their ID’s (no dillingerj ID’s found here). The FBI knows that each
criminal uses only one ID. The only other information they have which
will help them is a log of names of the people who enter and leave the
hideout. In many cases, this is enough to link the names to the ID’s.
Input
Input consists of
one problem instance. The first line contains a single positive integer n
indicating the number of criminals using the hideout. The maximum value
for n will be 20. The next line contains the n user ID’s, separated by
single spaces. Next will be the log entries in chronological order. Each
entry in the log has the form type arg , where type is either E, L or
M: E indicates that criminal arg has entered the hideout; L indicates
criminal arg has left the hideout; M indicates a message was intercepted
from user ID arg. A line containing only the letter Q indicates the end
of the log. Note that not all user ID’s may be present in the log but
each criminal name will be guaranteed to be in the log at least once. At
the start of the log, the hideout is presumed to be empty. All names
and user ID’s consist of only lowercase letters and have length at most
- Note: The line containing only the user ID’s may contain more than
80 characters.
Output
Output consists of n lines, each containing a list of
criminal names and their corresponding user ID’s, if known. The list
should be sorted in alphabetical order by the criminal names. Each line
has the form name:userid , where name is the criminal’s name and userid
is either their user ID or the string ??? if their user ID could not be
determined from the surveillance log.
Sample Input
7 <br></br>bigman mangler sinbad fatman bigcheese frenchie capodicapo <br></br>E mugsy <br></br>E knuckles <br></br>M bigman <br></br>M mangler <br></br>L mugsy <br></br>E clyde <br></br>E bonnie <br></br>M bigman <br></br>M fatman <br></br>M frenchie <br></br>L clyde <br></br>M fatman <br></br>E ugati <br></br>M sinbad <br></br>E moriarty <br></br>E booth <br></br>Q
Sample Output
Hint
bonnie:fatman
booth:???
clyde:frenchie
knuckles:bigman
moriarty:???
mugsy:mangler
ugati:sinbad
Source
这是一道二分图匹配的题目，一开始的时候想到了构图的办法，但是弄完图之后没有想到用二分图匹配，而是用了自己想出来的一个烂办法，结果就是WA，想到了一个反例又看了Discuss之后确信了用二分图匹配可以做。
构图方法是先置所有边为1，然后按顺序扫描输入，当某人发出一个信息的时候，说明只可能是当前正在房间里面的人发出信息，于是就把发出信息的这个人与所有不在房间里面的人连接的边删掉，之后就能得到一个二分图。
对于这个二分图，肯定是有一个完备匹配的。然后扫描二分图的每一条边，如果删了这条边之后不存在完备匹配说明这条边必须有，也就确定了一个name与id的关系了。
具体写的时候用了大量STL……发现STL还是挺方便的……就是一改C的简洁风格，每次写for(map<string, string>::iterator i = a.begin(); i!= a.end(); ++i)都感觉要崩溃……然后for_each又要自己写个函数类……单单这句话看起来是清爽了些，但是整体来看又是个乱七八糟的函数类，还是一次性的，每个循环都要写个函数类……悲剧……吐槽一下……不知道C++0x有没有改进……如果有了C#的lamda表达式之类的东西那应该方便很多……
另外好久没写匈牙利算法了，自己写出来之后感觉还行，也不是很乱，但是之后百度了一下别人的匈牙利算法……发现比我整整短了一倍……看起来也舒服……大悲剧……
贴代码先……
#include
#include <map>
#include
#include
using namespace std;
int n, nowIn[21], ans[21], now, a[21][21];//a[i][j]=0表示可能，1表示可能
int match[41], searched[41];
int dfs(int k)
{
for(int i=n+1; i<=n2; i++)
if(a[k][i-n] == 1 && match[i] == 0){
match[i] = k;
match[k] = i;
return i;
}
for(int i=n+1; i<=n2; i++)
if(a[k][i-n] == 1 && searched[i] == 0){
searched[k] = searched[i] = 1;
int ret = dfs(match[i]);
searched[k] = searched[i] = 0;
if(ret != 0){
match[i] = k;
match[k] = i;
return i;
}
}
return 0;
}
int pipei()
{
int ret = 0;
fill_n(match, 41, 0);
fill_n(searched, 41, 0);
for(int i=1; i<=n ; ++i){
if(dfs(i))
++ret;
}
return ret;
}
int main()
{
string name[21],ID[21];
map<string, int> name2n,ID2n;
cin » n;
for(int i=1; i<=n; i++){
cin » name[i];
name2n[name[i]] = i;
}
fill_n(nowIn, 21, 0);
fill_n(a[0], 21*21, 1);
string s1, s2;
now = 0;
while(true){
cin » s1;
if(s1 == “Q”)
break;
cin » s2;
if(s1 == “E”){
if(ID2n[s2] == 0){
ID2n[s2] = ++now;
ID[now] = s2;
}
nowIn[ID2n[s2]] = 1;
}
if(s1 == “L”)
nowIn[ID2n[s2]] = 0;
if(s1 == “M”) {
for (int i = 1; i <= n; ++i){
if (nowIn[i] == 0)
a[name2n[s2]][i] = 0;
}
}
}
fill_n(ans, 21, 0);
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++){
if(a[i][j] == 1){
a[i][j] = 0;
if(pipei() != n)
ans[i] = j;
a[i][j] = 1;
}
if(ans[i] != 0)
break;
}
}
map<string, string> aa;
int i = 0;
for(int i=1; i<=n; ++i)
aa[ID[i]] = “???”;
for(int i=1; i<=n; i++)
if(ans[i] != 0)
aa[ID[ans[i]]] = name[i];
for(map<string, string>::iterator j = aa.begin(); j!= aa.end(); ++j)
cout « j->first « ”:” « j->second « endl;
return 0;
}
贴上百度来的匈牙利算法
#include
#include
using namespace std;
int n1, n2, m, ans;
int result[101]; //记录V2中的点匹配的点的编号
bool state [101]; //记录V2中的每个点是否被搜索过
bool data[101][101];//邻接矩阵 true代表有边相连
void init()
{
int t1, t2;
memset(data, 0, sizeof(data));
memset(result, 0, sizeof(result));
ans = 0;
scanf(“
%d%d%d”, &n1, &n2, &m);
for (int i = 1; i <= m; i++)
{
scanf(“%d%d”, &t1, &t2);
data[t1][t2] = true;
}
return;
}
bool find(int a)
{
for (int i = 1; i <= n2; i++)
{
if (data[a][i] == 1 && !state[i]) //如果节点i与a相邻并且未被查找过
{
state[i] = true; //标记i为已查找过
if (result[i] == 0 //如果i未在前一个匹配M中
|| find(result[i])) //i在匹配M中，但是从与i相邻的节点出发可以有增广路
{
result[i] = a; //记录查找成功记录
return true; //返回查找成功
}
}
}
return false;
}
int main()
{
init();
for (int i = 1; i <= n1; i++)
{
memset(state, 0, sizeof(state)); //清空上次搜索时的标记
if (find(i)) ans++; //从节点i尝试扩展
}
printf(“%d\n”, ans);
return 0;
}
阅读全文
