| 角色扮演 |
| Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:32768KB |
| Total submit users: 26, Accepted users: 8 |
| Problem 10845 : No special judgement |
| Problem description |
| 某年轻导演准备拍摄一部名为《温柔石头》的喜剧电影。由于预算紧张导演绞尽脑汁想节省开支。作为剧务的你提醒他：“演员的出场费很高，能不能让他们一人分演多个角色？充分挖掘他们的潜力，也可以节省我们的开支嘛！”导演大呼“有创意”，并顺手把剧本塞给你,“你研究研究剧本，看最少需要几个演员”，说着就准备出门去再拉几个广告赞助商，临走前他又补充了几点要求： 1 男演员只能演男角色，女演员只能演女角色。 2 角色的扮演者确定下来后，在演出的过程中就不能中途更改。 3 如果两个角色会同时在一个场景中出现，则这两个角色必须由两个不同的演员扮演。 导演走后，你翻开剧本看了看，发现了一张场景清单，也就是本题目的输入文件。 |
| Input |
| 输入文件的第一行包含用空格分隔的3个正整数，M, F和S。 其中M代表剧中的男角色数目，取值在[1, 10]之间； F代表剧中的女角色数目，取值在[1, 10]之间； S代表剧中的场景数目，取值在[1, 100]之间。 第二行和第三行分别列出了男角色和女角色的名字，每个名字都是一个英文字符串，名字之间有空格分隔。 下面的S行分别描述了每个场景中出现的角色数和角色名（有空格分隔）。 |
| Output |
| 本剧需要的男女演员的最少数目，具体格式如下： “You need x actors and y actresses” 其中x和y分别代表男、女演员的最少数目 |
| Sample Input |
4 3 6 Tarzan Jim John Tom Lucy Cynthia Jane 3 Jim John Tom 2 Tarzan Lucy 2 Jane Cynthia 2 Jim Jane 2 Tarzan Jim 2 Tarzan Jane |
| Sample Output |
You need 3 actors and 2 actresses |
| Problem Source |
| 湖南省第二届程序设计大赛 |
经过几番郁闷后， AAACCC 了。。。。。
解题报告：
可能大家都知道这就是着色问题，更进一步地说是非平面的着色问题，经过分析转换后，可知主要就是求一个节点不大于十的图的最小着色。角色即为图的节点。首先我们可以将字符串（角色名字）转换为矩阵的下标，用两个矩阵分别保存男女角色的出场关系，如果在某一场演出中，a 角色和 b 角色同时出现（a,b 同为男或者女角色）则这两个角色的对应节点在图中是邻接的。得到图的邻接关系后，我们从编号为 0 的角色开始分配演员，演员的编号也从0 开始，因为一个演员可以扮演多个角色，因此我们需要再开一二维数组，记录某个演员扮演的所有角色编号。对于某个未分配演员的角色，我们有两种分配演员的方法，其一是分配一个新的演员，其二是从已经分配出的演员中找个没有冲突的演员（即图中不和该角色对应节点相邻的节点）。容易知道从已经分配出的演员搜索角色的扮演者最有可能获得最优解。因此为角色分配演员时，先从已经分配的演员里搜索。
相关知识：深度搜索， 递归， 分支限界
实现代码如下：
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
const int MAX_ROLE = 10;
int gdisp[MAX_ROLE][MAX_ROLE] = {0}, gBest = MAX_ROLE;
void get(bool bp[][MAX_ROLE], int s, int n, int idisp, int people){
int i,j,k;
for(i=s; i<n; i++){
for(j=0; j<idisp; j++){
for(k=1; k<=gdisp[j][0]; k++){
if(bp[i][gdisp[j][k]])
break;
}
if(k>gdisp[j][0]){
gdisp[j][++gdisp[j][0]] = i;
get(bp,i+1,n,idisp,people);
gdisp[j][0]--;
}
}
if(idisp<gBest){
gdisp[idisp][0]++;
gdisp[idisp++][1] = i;
people++;
}else
return;
}
if(people < gBest)
gBest = people;
}
int main(){
int m, f, s, i, j, k;
cin>>m>>f>>s;
vector<string> strVm,strVf;
strVm.resize(m);
strVf.resize(f);
for(i=0; i<m; i++)
cin>>strVm[i];
for(i=0; i<f; i++)
cin>>strVf[i];
int mfind[MAX_ROLE], ffind[MAX_ROLE], mf, ff;
bool bm[MAX_ROLE][MAX_ROLE] = {false}, bf[MAX_ROLE][MAX_ROLE] = {false};
string str;
vector<string>::iterator it;
for(i=0; i<s; i++){
cin>>j;
for(mf=ff=k=0; k<j; k++){
cin>>str;
if((it=find(strVm.begin(),strVm.end(),str))!=strVm.end())
mfind[mf++] = (int)(it-strVm.begin());
else{
it=find(strVf.begin(),strVf.end(),str);
ffind[ff++] = (int)(it-strVf.begin());
}
}
for(j=0; j<mf; j++)
for(k=j+1; k<mf; k++)
bm[mfind[j]][mfind[k]] = bm[mfind[k]][mfind[j]] = true;
for(j=0; j<ff; j++)
for(k=j+1; k<ff; k++)
bf[ffind[j]][ffind[k]] = bf[ffind[k]][ffind[j]] = true;
}
get(bm, 0, m, 0, 0);
mf = gBest;
for(gBest=MAX_ROLE, i=0; i < f; i++)
gdisp[i][0] = 0;
get(bf, 0, f, 0, 0);
cout<<"You need "<<mf<<" actors and "<<gBest<<" actresses"<<endl;
return 0;
}
| 2 | 138166 | MSN | GNU C++ | 1104KB | 0ms | 1812B |
评论