admin 管理员组

文章数量: 1087817

一本通1362：家庭问题(family)最通俗解法

1362：家庭问题(family)


时间限制: 1000 ms         内存限制: 65536 KB
提交数: 4558     通过数: 2350

【题目描述】

有n个人，编号为1,2,……n，另外还知道存在K个关系。一个关系的表达为二元组（α，β）形式，表示α，β为同一家庭的成员。

当n，k和k个关系给出之后，求出其中共有多少个家庭、最大的家庭中有多少人？

例如：n＝6，k＝3，三个关系为（1,2），(1,3)，(4,5)

此时，6个人组成三个家庭，即：｛1,2,3｝为一个家庭，｛4,5｝为一个家庭，｛6｝单独为一个家庭，第一个家庭的人数为最多。

【输入】

第一行为n,k二个整数（1≤n≤100）（用空格分隔）;

接下来的k行，每行二个整数（用空格分隔）表示关系。

【输出】

二个整数（分别表示家庭个数和最大家庭人数）。

【输入样例】

6  3
1  2
1  3
4  5

【输出样例】

3 3

对于这道题，有人用队列，有人用并查集，那我这个方法叫什么呢

很单纯的方法

好吧

每次输入数据都不断更新，这个更新的过程很重要！

最后遍历一次得到答案

代码1.

最优代码：（其实可以不用快读）

解法采用以空间换取时间

#include<cstdio>
int family[101][101]; //family[i][0]存儿子数量 [i][1,2,3...]为他的儿子
int visited[101][2];  //visited[i][0]表示是否已有家庭 [1]存他的家庭是谁
inline int read()     //快读
{int s=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}return s*f;
}
signed main(){int m,n;int c,t;int total=0;m=read(),n=read();for(int i=1;i<=n;i++){c=read();t=read();if(!visited[c][0] && !visited[t][0]){ if(c>0 && c<=m || t<=m && t>0){total++;}if(c>0 && c<=m ){           //情况1.1visited[c][0]=true;family[total][1]=c;family[total][0]++;visited[c][1]=total;}if(c!=t && t<=m && t>0){	//情况1.2	 visited[t][0]=true;family[total][2]=t;		    family[total][0]++;	visited[t][1]=total;}}else{                           if(visited[c][0]){            //情况2.1if(visited[t][0])continue;visited[t][0]=true;visited[t][1]=visited[c][1];family[visited[c][1]][0]++;int s=family[visited[c][1]][0];family[visited[c][1]][s]=t;}else if(visited[t][0]){        //情况2.2visited[c][0]=1;visited[c][1]=visited[t][1];family[visited[t][1]][0]++;int s=family[visited[t][1]][0];family[visited[t][1]][s]=c;}}}int last=0;   //单独成员for(int i=1;i<=m;i++){if(!visited[i][0]){last++;}}last+=total;int max=1;    //最多儿子for(int i=1;i<=total;i++){if(family[i][0]>max){max=family[i][0];}}printf("%d %d",last,max);return 0;
}

程序运行结果


用户名:MaryL，题目编号:1362，运行编号:12509742，代码长度:1571Bytes

通过

测试点结果内存时间
测试点1答案正确260KB4MS
测试点2答案正确264KB4MS
测试点3答案正确264KB4MS
测试点4答案正确264KB4MS
测试点5答案正确268KB2MS

代码2.(第一次通过的代码)

#include<cstdio>
#include<iostream>
using namespace std;
int family[1000][1000];
int visited[1000][2];
int main(){int m,n;int c,t;int total=0;scanf("%d %d",&m,&n);for(int i=1;i<=n;i++){scanf("%d %d",&c,&t);if(!visited[c][0] && !visited[t][0]){if(c>0 && c<=m || t<=m && t>0){total++;}if(c>0 && c<=m ){visited[c][0]=true;family[total][1]=c;family[total][0]++;visited[c][1]=total;}if(c!=t && t<=m && t>0){		 visited[t][0]=true;family[total][2]=t;		    family[total][0]++;	visited[t][1]=total;}}else{if(visited[c][0]){if(visited[t][0])continue;visited[t][0]=true;visited[t][1]=visited[c][1];family[visited[c][1]][0]++;int s=family[visited[c][1]][0];family[visited[c][1]][s]=t;}else if(visited[t][0]){visited[c][0]=1;visited[c][1]=visited[t][1];family[visited[t][1]][0]++;int s=family[visited[t][1]][0];family[visited[t][1]][s]=c;}}}int last=0;for(int i=1;i<=m;i++){if(!visited[i][0]){last++;}}last+=total;int max=-1;for(int i=1;i<=total;i++){if(family[i][0]>max){max=family[i][0];}}printf("%d %d",last,max);return 0;
}

【1362】程序运行结果


用户名:MaryL，题目编号:1362，运行编号:12509785，代码长度:1403Bytes

通过
 

测试点结果内存时间
测试点1答案正确456KB7MS
测试点2答案正确440KB5MS
测试点3答案正确452KB6MS
测试点4答案正确452KB6MS
测试点5答案正确468KB4MS

本文标签： 一本通1362家庭问题(family)最通俗解法

版权声明：本文标题：一本通1362：家庭问题(family)最通俗解法 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/p/1700275700a375686.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。