「CODEVS1002」搭桥

2014年2月4日5,2350

题目描述 Description

有一矩形区域的城市中建筑了若干建筑物，如果某两个单元格有一个点相联系，则它们属于同一座建筑物。现在想在这些建筑物之间搭建一些桥梁，其中桥梁只能沿着矩形的方格的边沿搭建，如下图城市1有5栋建筑物，可以搭建4座桥将建筑物联系起来。城市2有两座建筑物，但不能搭建桥梁将它们连接。城市3只有一座建筑物，城市4有3座建筑物，可以搭建一座桥梁联系两栋建筑物，但不能与第三座建筑物联系在一起。

输入描述 Input Description

在输入的数据中的第一行包含描述城市的两个整数r 和c, 分别代表从北到南、从东到西的城市大小(1 <= r <= 50 and 1 <= c <= 50). 接下来的r 行, 每一行由c 个(“#”)和(“.”)组成的字符. 每一个字符表示一个单元格。“#”表示建筑物，“.”表示空地。

输出描述 Output Description

在输出的数据中有两行，第一行表示建筑物的数目。第二行输出桥的数目和所有桥的总长度。

样例输入 Sample Input

样例1

3 5

#…#

..#..

#…#

样例2

3 5

##…

…..

….#

样例3

3 5

#.###

#.#.#

###.#

样例4:

3 5

#.#..

…..

….#

样例输出 Sample Output

样例1

5

4 4

样例2

2

0 0

样例3

1

0 0

样例4

3

1 1

数据范围及提示 Data Size & Hint

见描述

代码

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,mark[51][51],cnt,ans,sum,father[2001];
bool mp[51][51];
int xx[8]={0,0,1,1,1,-1,-1,-1},
    yy[8]={1,-1,0,1,-1,0,1,-1};
struct data{int x,y,v;}e[100001];
inline bool cmp(data a,data b){return a.v<b.v;}
int find(int x){return x==father[x]?x:father[x]=find(father[x]);}
bool insert(int x1,int y1,int x2,int y2,int v)
{
     if(y2<1||y2>m||x2<1||x2>n||!mark[x2][y2])return 1;
     if(mark[x1][y1]==mark[x2][y2])return 0;
     cnt++;
     e[cnt].x=mark[x1][y1];
     e[cnt].y=mark[x2][y2];
     e[cnt].v=v-1;
     return 1;
     }
int dfs(int x,int y)
{
    mark[x][y]=ans;
    for(int i=0;i<8;i++)
    {
            int nowx=x+xx[i],nowy=y+yy[i];
            if(mp[nowx][nowy]&&!mark[nowx][nowy])
                dfs(nowx,nowy);
            }
    }
void work1()
{
     ans=0;
     for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
           if(mp[i][j]&&!mark[i][j]){ans++;dfs(i,j);}
     printf("%d\n",ans);
     }
void build(int x,int y)
{
     for(int i=x+1;i<=n;i++)
         if(!insert(x,y,i,y,i-x)||!insert(x,y,i,y+1,i-x)||!insert(x,y,i,y-1,i-x))
             break;
     for(int i=x-1;i>0;i--)
         if(!insert(x,y,i,y,x-i)||!insert(x,y,i,y+1,x-i)||!insert(x,y,i,y-1,x-i))
             break;
     for(int i=y+1;i<=m;i++)
         if(!insert(x,y,x,i,i-y)||!insert(x,y,x-1,i,i-y)||!insert(x,y,x+1,i,i-y))
             break;
     for(int i=y-1;i>0;i--)       
         if(!insert(x,y,x,i,y-i)||!insert(x,y,x-1,i,y-i)||!insert(x,y,x+1,i,y-i))
             break; 
     }
void work2()
{
     for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
           if(mp[i][j])build(i,j);
     sort(e+1,e+cnt+1,cmp);
     for(int i=1;i<=ans;i++)father[i]=i;
     ans=0;
     for(int i=1;i<=cnt;i++)
     {
             int p=find(e[i].x),q=find(e[i].y);
             if(p!=q){father[p]=q;ans++;sum+=e[i].v;}
             }
     printf("%d %d\n",ans,sum);
     }
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
            char ch[60];
            scanf("%s",ch);
            for(int j=1;j<=m;j++)
               if(ch[j-1]=='#')mp[i][j]=1;
            }
    work1();
    work2();
    return 0;
    }

#include<iostream>

#include<cstdio>

#include<algorithm>

using namespace std;

int n,m,mark[51][51],cnt,ans,sum,father[2001];

bool mp[51][51];

int xx[8]={0,0,1,1,1,-1,-1,-1},

yy[8]={1,-1,0,1,-1,0,1,-1};

struct data{int x,y,v;}e[100001];

inline bool cmp(data a,data b){return a.v<b.v;}

int find(int x){return x==father[x]?x:father[x]=find(father[x]);}

bool insert(int x1,int y1,int x2,int y2,int v)

{

if(y2<1||y2>m||x2<1||x2>n||!mark[x2][y2])return 1;

if(mark[x1][y1]==mark[x2][y2])return 0;

cnt++;

e[cnt].x=mark[x1][y1];

e[cnt].y=mark[x2][y2];

e[cnt].v=v-1;

return 1;

}

int dfs(int x,int y)

{

mark[x][y]=ans;

for(int i=0;i<8;i++)

{

int nowx=x+xx[i],nowy=y+yy[i];

if(mp[nowx][nowy]&&!mark[nowx][nowy])

dfs(nowx,nowy);

}

void work1()

{

ans=0;

for(int i=1;i<=n;i++)

for(int j=1;j<=m;j++)

if(mp[i][j]&&!mark[i][j]){ans++;dfs(i,j);}

printf("%d\n",ans);

}

void build(int x,int y)

{

for(int i=x+1;i<=n;i++)

if(!insert(x,y,i,y,i-x)||!insert(x,y,i,y+1,i-x)||!insert(x,y,i,y-1,i-x))

break;

for(int i=x-1;i>0;i--)

if(!insert(x,y,i,y,x-i)||!insert(x,y,i,y+1,x-i)||!insert(x,y,i,y-1,x-i))

break;

for(int i=y+1;i<=m;i++)

if(!insert(x,y,x,i,i-y)||!insert(x,y,x-1,i,i-y)||!insert(x,y,x+1,i,i-y))

break;

for(int i=y-1;i>0;i--)

if(!insert(x,y,x,i,y-i)||!insert(x,y,x-1,i,y-i)||!insert(x,y,x+1,i,y-i))

break;

}

void work2()

{

for(int i=1;i<=n;i++)

for(int j=1;j<=m;j++)

if(mp[i][j])build(i,j);

sort(e+1,e+cnt+1,cmp);

for(int i=1;i<=ans;i++)father[i]=i;

ans=0;

for(int i=1;i<=cnt;i++)

{

int p=find(e[i].x),q=find(e[i].y);

if(p!=q){father[p]=q;ans++;sum+=e[i].v;}

}

printf("%d %d\n",ans,sum);

}

int main()

{

scanf("%d%d",&n,&m);

for(int i=1;i<=n;i++)

{

char ch[60];

scanf("%s",ch);

for(int j=1;j<=m;j++)

if(ch[j-1]=='#')mp[i][j]=1;

}

work1();

work2();

return 0;

}

« 无聊写的A+B问题。。。「usaco2002.4」Chores »

hzwer.com _ Home | http://hzwer.com

「CODEVS1002」搭桥

题目描述 Description

输入描述 Input Description

输出描述 Output Description

样例输入 Sample Input

样例输出 Sample Output

数据范围及提示 Data Size & Hint

代码

分类目录

热门文章

Myfriends

近期评论