大致题意:
给你两个长度相同的字符串,问这两个串中的字母怎么样匹配才能使得总的复合度最大。
大致思路:
按照字母间的对应关系建二分图,求出最大全匹配后除以总长度。
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int nMax=55;
const int mMax=10005;
const int inf=1<<29;
int map[nMax][nMax];
int lx[nMax],ly[nMax];
int mapch[nMax];
int stack[nMax];
bool sy[nMax],sx[nMax];
int n,m,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 num[mMax],sub[mMax];
int main(){
int cas,i,j,N,M,K;
char sss[3];
n=m=26;
scanf("%d",&cas);
while(cas--){
scanf("%d%d%d",&N,&M,&K);
for(i=1;i<=N;i++){
scanf("%s",sss);
num[i]=sss[0]-'A'+1;
}
while(K--){
for(i=1;i<=N;i++){
scanf("%s",sss);
sub[i]=sss[0]-'A'+1;
}
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
map[i][j]=0;
}
}
for(i=1;i<=N;i++){
map[sub[i]][num[i]]++;
}
double ans=KM();
ans/=(N*1.0);
printf("%.4f\n",ans);
}
}
return 0;
}
分享到:
相关推荐
Problem Description Calculate A + B. Input Each line will contain two integers A and B....HDOJ 代码: #include int main() { int a,b; while(scanf("%d %d",&a,&b)!=EOF) printf("%d\n",a+b); }
HDOJ题目分类HDOJ题目分类HDOJ题目分类
leetcode和hdoj 简介 主要用来记录算法刷题记录和一些模板 文件结构 leetcode 存放leetcode题目和周赛 atcoder 用于存放参与和vp的atcoder比赛 codeforces 用于存放参与和vp的cf比赛,比赛文件夹以比赛序号和div描述...
ACM ICPC HDOJ1002
ACM ICPC HDOJ1001
hdoj1001标程
hdoj上的资源,代码有注释,很不错的哦
hdoj-problem-archive 杭电OJ题目源码记录 —— a source code of hdoj acm problem archive 简介 此项目为 的 题目以及代码仓库 src 中每一个文件夹代表一个题目 每个文件夹中都有 原题文档介绍.md 原题文档介绍.md...
hdoj1004,解题代码,答案代码,欢迎下载
ACM ICPC HDOJ1003
ACM ICPC HDOJ1008
杭州电子科技大学hdoj1002,大整数相加问题
杭州电子科大HDOJ
kmp算法 KMP算法是一种用于在一个文本串S中查找一个模式串P出现位置的高效算法。KMP算法的核心思想是利用模式串P本身的信息来避免在文本串S中进行不必要的匹配。具体来说,KMP算法通过预处理模式串P,构建一个部分...
c语言 最短路 是hdoj上的一个最短路问题,写的很牛
ACM ICPC HDOJ1000
hdoj解题代码,题目为1000-1050
一些HDOJ上的DP题目的小总结,但愿能帮到那些想专攻DP的人吧
codj,hdoj的源码(50-60题)
hdoj 2013 多校训练3标程+解题报告