首页 > 代码库 > HDU 4185

HDU 4185

2024-07-12 17:54:28   218人阅读

http://acm.hdu.edu.cn/showproblem.php?pid=4185

两个挨着的‘#‘可以配成一对，求最多能配成几对

挨着的‘#‘就连边，然后求一次最大匹配，答案是最大匹配除以二（因为1 2和2 1这两对匹配实际效果是1，但是会算成2）

#include <iostream>#include <cstdio>#include <cstring>using namespace std ;struct node{    int s,t,nxt ; }e[500005] ;int m,n,head[500005],cnt,match[500005],vis[500005] ;int find(int s){    for(int i=head[s] ;i!=-1 ;i=e[i].nxt)    {        int tt=e[i].t ;        if(!vis[tt])        {            vis[tt]=1 ;            if(match[tt]==-1 || find(match[tt]))            {                match[tt]=s ;                return 1 ;            }        }    }    return 0 ;}int max_match(){    int ans=0 ;    memset(match,-1,sizeof(match)) ;    for(int i=1 ;i<=m ;i++)    {        memset(vis,0,sizeof(vis)) ;        ans+=find(i);    }    return ans;}void add(int s,int t) {e[cnt].s=s ;e[cnt].t=t ;e[cnt].nxt=head[s] ;head[s]=cnt++ ;}char M[605][605] ;int mp[605][605] ;int dx[]={1,-1,0,0} ;int dy[]={0,0,1,-1} ;int main(){    int T ;    scanf("%d",&T) ;    for(int cas=1 ;cas<=T ;cas++)    {        int N ;        scanf("%d",&N) ;        for(int i=0 ;i<N ;i++)            scanf("%s",M[i]) ;        n=0 ;        memset(mp,0,sizeof(mp)) ;        for(int i=0 ;i<N ;i++)        {            for(int j=0 ;j<N ;j++)            {                if(M[i][j]==‘#‘)                {                    n++ ;                    mp[i][j]=n ;                }            }        }        memset(head,-1,sizeof(head)) ;        cnt=0 ;        for(int i=0 ;i<N ;i++)        {            for(int j=0 ;j<N ;j++)            {                if(M[i][j]==‘#‘)                {                    for(int k=0 ;k<4 ;k++)                    {                        int xx=i+dx[k] ;                        int yy=j+dy[k] ;                        if(xx<0 || xx>=N || yy<0 || yy>=N)continue ;                        if(mp[xx][yy])                        {                            add(mp[i][j],mp[xx][yy]) ;                        }                    }                }            }        }        m=n ;        printf("Case %d: %d\n",cas,max_match()/2) ;    }    return 0 ;}
View Code


联系
我们