大致题意:
有n个男生,m个女生,每个人用一句话描述其他的异性。对与第i个人和第j个异性,其好感值为其姓名第一次出现的位置和出现次数的乘积。现在要匹配这些人,使得总的好感值之和最大,求这个值。
大致思路:
kmp算法加km。km模版有点问题,n不能小于m,所以加了一句n=m=max(n,m)糊弄过去了。
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
char name[300][50],str[300][20000];
const int nMax=300;
const int mMax=20005;
const int inf=1<<30;
int map[300][300];
int n,m;
//char text[mMax],pat[nMax];
int lent,lenp,next[nMax];
void get_next(char *pat){
int i,j=-1;
next[0]=-1;
for(i=1;i<=lenp;i++){ //pat[j]是不是可以理解为i的前一个字符的next值所指想的字符
while(j>-1&&pat[j+1]!=pat[i])j=next[j];
if(pat[j+1]==pat[i])j++;
next[i]=j;
}
}
int KMP(char *pat,char *text,int &pos){
int ans=0,i=0,j=-1;
// get_next();
bool flag=1;
for(i=0;i<lent;i++){
while(j!=-1&&pat[j+1]!=text[i]){
j=next[j];
}
if(pat[j+1]==text[i])j=j+1;
if(j==lenp-1)
{
if(flag)
{
pos=i;
flag=0;
}
ans++; //找到一个匹配
}
}
return ans;
}
int solve(int a,int b)
{
int i,j,c,fp;
// for(i=0;i<strlen(str[a]);i++)
// {
// text[i]=str[a][i];
// }
// text[strlen(str[a])]='\0';
// for(i=0;i<strlen(name[b]);i++)
// {
// pat[i]=name[b][i];
// }
// pat[strlen(name[b])]='\0';
lenp=strlen(name[b]);
lent=strlen(str[a]);
get_next(name[b]);
c=KMP(name[b],str[a],fp);
if(c==0)fp=1;
else{
fp=fp-strlen(name[b]);
fp+=2;
}
// cout<<a<<" "<<b<<" "<<fp<<" "<<c<<endl;
return (fp)*c;
}
int lx[nMax],ly[nMax];
int mapch[nMax];
int stack[nMax];
bool sy[nMax],sx[nMax];
int e,cnt;
int find (int u){
int v,t;
sx[u]=1;
for(v=1;v<=m;v++){
if(sy[v]) continue;
t=lx[u]+ly[v]-map[u][v];
if(t==0){
sy[v]=1;
if(mapch[v]==-1||find(mapch[v])){
mapch[v]=u;
return 1;
}
}
else if(t<stack[v]) stack[v]=t;
}
return 0;
}
int KM(){
int i,j,k,d,sum=0;
cnt=0;
for(i=1;i<=m;i++)
ly[i]=0;
memset(mapch,-1,sizeof(mapch));
for(i=1;i<=n;i++){
lx[i]=-inf;
for(j=1;j<=m;j++)
if(map[i][j]>lx[i])
lx[i]=map[i][j];
}
for(i=1;i<=n;i++){
for(j=1;j<=m;j++)
stack[j]=inf;
while(1){
for(k=1;k<=m;k++) sy[k]=0;
for(k=1;k<=n;k++) sx[k]=0;
if(find(i)) break;
d=inf;
for(k=1;k<=m;k++)
if(!sy[k]&&stack[k]<d)
d=stack[k];
for(k=1;k<=n;k++)
if(sx[k]) lx[k]-=d;
for(k=1;k<=m;k++)
if(sy[k]) ly[k]+=d;
else stack[k]-=d;
}
}
for(i=1;i<=m;i++)
if(mapch[i]!=-1&&map[mapch[i]][i]!=-inf){
sum+=map[mapch[i]][i];
}
return sum;
}
int main()
{
int i,j;
while(cin>>n>>m)
{
memset(map,0,sizeof(map));
for(i=1;i<=m+n;i++)
{
cin>>name[i];
getchar();
name[i][strlen(name[i])-1]='\0';
gets(str[i]);
}
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{
map[i][j]+=solve(i,j+n);
map[i][j]+=solve(j+n,i);
}
n=m=max(n,m);
cout<<KM()<<endl;
}
return 0;
}
分享到:
相关推荐
acm 模板 算法 浙大 zoj zju acm初学者必备 代码
每一个都有代码和注释,分析,很好的算法练习 实验一:递归与分治 1. 二分查找 2. 合并排序 3. 快速排序 实验二:回溯 1. 0-1背包问题 2. 装载问题 3. 堡垒问题(ZOJ1002) 4. *翻硬币问题 5. 8皇后问题 6. 素数环...
ZOJ解题报告ZOJ解题报告ZOJ解题报告ZOJ解题报告
zoj题目简单归类zoj题目简单归类zoj题目简单归类
学习ACM程序设计的朋友一定要看,这是训练必备的POJ ZOJ题目分类及解题思路
acm中zoj1002的可运行C++程序
ZOJ题目答案源码
包含了zoj700多道题目的源代码,在做题时可以参考
zoj 3049 Diablo II Items.md
Problem Arrangement zoj 3777
一个非常非常非常非常实用的zoj结题代码
ZOJ1805代码
zoj 1003 c语言的,要写这么多描述吗。。
本代码是zoj上AC的1951的代码,把双重循环简化为O(n),不过素数判断的改进还不够
这是一份ZOJ的ACM题解,包含大多数题目的AC程序,是学习算法的好东西~
zoj1027解题指南和代码,还不错,是学校培训给的。
浙大ZOJ题目分类,可以让你更方便快速锁定那你想要联系的题目,是自己快速提高·
ZOJ题解集合-截至2835。共1244个文件,C/C++,有重复
zoj 题库 详细解答 解题代码 acm
zoj4041正确题解源代码,以及运行程序