IT学习联盟

 找回密码
 立即注册
搜索
热搜: 活动 交友 discuz
IT学习联盟 门户 文章 ASP.NET/C# 查看内容

hdu 1528 Card Game Cheater (最小覆盖)

2012-8-18 03:07| 发布者: admin| 查看: 567| 评论: 0

给定A,B两组牌,让找出B最多能的多少分
首先对牌的字符串全部转化成十进制数,然后以数字为点,
B集合元素相对于A集合数字的大小关系为边,显然是典型的最小顶点覆盖问题
[csharp] 
#include"stdio.h" 
#include"string.h" 
#define N 52 
int map[N][N],v[N],link[N]; 
int A[N],B[N],t,n; 
int dfs(int k) 

    int i; 
    for(i=1;i<=n;i++) 
    { 
        if(map[k][i]&&!v[i]) 
        { 
            v[i]=1; 
            if(link[i]==0||dfs(link[i])) 
            { 
                link[i]=k; 
                return 1; 
            } 
        } 
    } 
    return 0; 

int main() 

    char c,d,e; 
    int i,j,vv,flag,ans; 
    int ap,bp; 
     
    scanf("%d",&t); 
    while(t--) 
    { 
        scanf("%d",&n); 
        getchar(); 
        flag=1; 
        ap=bp=0; 
        for(i=0;i<2*n;i++) 
        { 
            scanf("%c%c%c",&c,&d,&e); 
            if(c>='0'&&c<='9') 
                vv=c-'0'; 
            if(c=='T')vv=10; 
            if(c=='J')vv=11; 
            if(c=='Q')vv=12; 
            if(c=='K')vv=13; 
            if(c=='A')vv=14; 
            vv*=100; 
            if(d=='H')vv+=4; 
            if(d=='S')vv+=3; 
            if(d=='D')vv+=2; 
            if(d=='C')vv+=1; 
            if(flag) 
                A[++ap]=vv; 
            else 
                B[++bp]=vv; 
            if(e=='\n') 
                flag=0; 
        } 
        memset(map,0,sizeof(map)); 
        for(i=1;i<=n;i++) 
        { 
            for(j=1;j<=n;j++) 
            { 
                if(A[i]<B[j]) 
                    map[j][i]=1; 
            } 
        } www.2cto.com
        memset(link,0,sizeof(link)); 
        ans=0; 
        for(i=1;i<=n;i++) 
        { 
            memset(v,0,sizeof(v)); 
            if(dfs(i)) 
                ans++; 
        } 
        printf("%d\n",ans); 
    } 
    return 0; 

 


Archiver|IT学习联盟| 网站地图

Powered by Discuz! X2.5© 2001-2010 世界学习室 大伟制作

GMT+8, 2018-8-16 04:15 , Processed in 0.088420 second(s), 12 queries .