`
暴风雪
  • 浏览: 387683 次
  • 性别: Icon_minigender_2
  • 来自: 杭州
社区版块
存档分类
最新评论

[看毛片算法][KM]zoj 3615:Choir II

阅读更多

大致题意:
    有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;
}
 
0
3
分享到:
评论
3 楼 proverbs 2012-09-08  
这样不好吧。。kmp被玷污了。。。 
2 楼 hejianmingwshjmcj 2012-09-04  
楼主看得太多了吧,研究这么透彻
1 楼 xiaoliouc 2012-09-04  
KMP=看毛片,博主太有才了

相关推荐

    ZOJ:浙江大学程序在线评测系统.docx

    ZOJ,全称“浙江大学程序在线评测系统”(Zhejiang University Online Judge),是一个提供信息学(算法竞赛)题库及程序评测的网站。以下是关于ZOJ的详细介绍: 一、基本信息 名称:浙江大学程序在线评测系统(ZOJ)...

    zoj 1002_zoj1002_

    题目编号1002,通常表示该题是ZOJ平台上的一个问题,可能涉及算法、数据结构或特定编程技巧的运用。 【描述】"ACM中ZOJ1002的可运行C++程序" 提示我们,这个压缩包包含了一个用C++语言编写的程序,该程序是为了解决...

    zoj 源码700题

    【标题】"zoj 源码700题"是指一个包含700多道ZOJ(在线判题系统Zhejiang Online Judge)编程竞赛题目的源代码集合。这个资源对于学习算法、提高编程技能以及准备编程竞赛的学员来说极具价值。 【描述】"包含了zoj...

    ZOJ题目答案源码

    ZOJ(Zhejiang Online Judge)是一个著名的在线编程竞赛平台,主要面向计算机科学与信息技术的学生和爱好者,提供了大量的算法题目供参赛者练习和提交代码。"ZOJ题目答案源码"是一个压缩包文件,其中包含了700多道...

    zoj.rar_zoj_zoj4041

    1. **算法选择**:在解决ZOJ 4041时,选择正确的算法至关重要。可能是动态规划、贪心策略、回溯法或者图论中的某一种。每种算法都有其特定的应用场景,选择最能适应问题特性的算法是优化解决方案的关键。 2. **时间...

    zoj.zip_zoj

    3. **搜索算法**:深度优先搜索(DFS)、广度优先搜索(BFS)、A* 搜索、Dijkstra 算法、Floyd-Warshall 算法等,这些是解决图论问题和路径查找的关键。 4. **动态规划**:背包问题、最长公共子序列、最短路径、...

    zoj1027解题指南

    ZOJ,全称为“Zhejiang Online Judge”,是浙江大学主办的一个在线编程竞赛平台,提供了丰富的算法题目供参赛者练习和挑战。本解题指南可能包含了对该题目的深入解析、思路引导、算法设计以及优化建议,旨在帮助参赛...

    zoj 题库 详细解答 解题代码

    该资源主要涵盖了 zoj 题库中的各种编程题目,涵盖了基本算法、数据结构、数学运算等多个方面的知识点。下面是对该资源中出现的知识点的详细解释: 1. 第一次 ACM 总结(7th ACM) 该题目主要考察了基本的算法设计...

    ZOJ月赛 题解 (ZOJ Monthly, August 2014)

    **ZOJ月赛题解 (ZOJ Monthly, August 2014)** ZOJ(Zhejiang Online Judge)是中国著名的在线编程竞赛平台之一,它为程序员和学生提供了丰富的算法练习和比赛机会。2014年8月的ZOJ月赛是一场面向广大编程爱好者的...

    zoj 700源代码

    ZOJ,全称为Zhejiang Online Judge,是一个知名的在线编程竞赛平台,主要服务于浙江大学和国内其他高校的学生,提供丰富的算法题目供参赛者练习和比赛。这个压缩包文件名为"ZOJ 700多题源代码",意味着它包含了解决...

    ZOJ题解集合-截至2835

    ZOJ(Zhejiang Online Judge)是一个著名的在线编程竞赛平台,尤其在ACM(国际大学生程序设计竞赛)领域中有着广泛的影响力。这个“ZOJ题解集合-截至2835”显然是一份包含了大量ZOJ题目解决方案的压缩包,其中涵盖了...

    浙江大学ZOJ题目分类

    浙江大学ZOJ(Zhejiang University Online Judge)是一个在线编程练习平台,主要服务于计算机科学和技术的学习者,特别是对算法和编程有浓厚兴趣的学生。这个平台提供了大量的编程题目,涵盖了各种难度和主题,帮助...

    pku hdu zoj题目分类

    本资料包聚焦于三大OJ平台——PKU(北京大学)、HDOJ(杭州电子科技大学)和ZOJ(浙江大学),它们都提供了丰富的题目资源,尤其是针对不同算法的分类,对于学习和准备ACM(国际大学生程序设计竞赛)或者其他算法...

    ZJU/zoj 题库上的部分题源码

    【标题】"ZJU/zoj 题库上的部分题源码"涉及的知识点主要集中在ACM(国际大学生程序设计竞赛)编程领域,尤其是浙江大学(ZJU)ZOJ(Zhejiang University Online Judge)题库中的题目解决方案。ZOJ是一个在线编程评测...

    zoj代码集合

    【ZOJ代码集合】是一个专为ACM(国际大学生程序设计竞赛)爱好者准备的资源库,其中包含了丰富的算法实现和编程技巧。这个压缩包文件名“ZOJ入门与提高代码集”暗示了它旨在帮助初学者逐步提升编程能力,同时也为有...

    zoj.gz_ ZOJ_ZOJ 1016_max flow_zoj 1045_zoj.rar

    标题中的"ZOJ.gz_ ZOJ_ZOJ 1016_max flow_zoj 1045_zoj.rar" 提到了两个ZOJ(Zhejiang Online Judge)的题目,分别是1016和1045,这两个数字通常代表在线编程竞赛中的题目编号。这些题目通常涉及到算法和数据结构的...

    浙大zoj月赛解题报告及代码

    【标题】"浙大ZOJ月赛解题报告及代码"揭示了这是一份与浙江大学ZOJ在线评测系统相关的竞赛编程资源,特别是针对月度竞赛的解题总结和实现代码。ZOJ,全称为Zhejiang University Online Judge,是浙江大学维护的一个...

    ZOJ.zip_Jugs A_ZOJ NTA_zoj acm_zoj acm 1216_zoj code

    【Jugs A】可能是指ZOJ中的一个特定问题,通常在ACM竞赛中,题目会被分为不同的难度等级,"A"可能是代表初级或简单的级别。这个问题可能涉及到实际生活中的数学问题,比如水壶倒水的问题,需要通过编程来解决如何将...

    ACM训练必备POJ ZOJ题目分类及解题思路

    学习ACM程序设计的朋友一定要看,这是训练必备的POJ ZOJ题目分类及解题思路

Global site tag (gtag.js) - Google Analytics