BZOJ_3632: 外太空旅行

6
17
2014

3632: 外太空旅行

Time Limit: 5 Sec Memory Limit: 128 MB
Submit: 123 Solved: 28
[Submit][Status]

Description

在人类的触角伸向银河系的边缘之际，普通人上太空旅行已经变得稀松平常了。某理科试验班有n个人，现在班主任要从中选出尽量多的人去参加一次太空旅行活动。

可是n名同学并不是和平相处的。有的人，比如小A和小B整天狼狈为奸，是好朋友；但还有的人，比如杜鲁门和赫鲁晓夫就水火不相容。这n名同学，由于是理科生，都非常的理性，所以“朋友的朋友就是朋友”和“敌人的朋友就是敌人”这两句话对这些同学无效。换句话说，有可能小A和小B是朋友，小B和小C是朋友，但是小A和小C两人势如水火。

任意两个人之间要不就是敌人，要不就是朋友。

因为在太空船上发生人员斗殴事件是很恶劣也很危险的，因此选出来参加旅行活动的同学必须互相之间都是朋友。你的任务就是确定最多可以选多少人参加旅行。

Input

第一行一个整数n(1<=n<=50)。所有的同学按照1~n编号。

接下来若干行，每行两个用空格隔开的整数a, b(1<=a,b<=n)，表示a和b是朋友。

注意：如果一个数对(x,y)（或者(y,x)）没有在文件中出现，那么编号为x和y的两个同学就是敌人。

Output

仅仅一个数，即最多可以选多少人参加活动。

Sample Input

4
1 2
2 3
3 1
1 4

Sample Output

3
说明：选编号为1,2,3的同学参加，他们互相都是朋友

最大团问题，好吧没别的了……

写题解的目的是为了推荐一篇博客，里面的做法跑的飞起……

http://www.cnblogs.com/zhj5chengfeng/archive/2013/07/29/3224092.html

简单说一下：

枚举第一个点，把连同的点放入集合q[1]；

在q[1]中枚举第2个点，把这个点在q[1]中连同的点放入集合q[2]；

…………………………

直到集合为空。

利用枚举顺序进行剪枝……

具体看那篇博客吧

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <cstdlib>
#include <set>
using namespace std;
int way[105][105],a,b,c,d,e,f[105],g,h,i,j,k,l,m,n,q[105][105],ans;
inline int maxx(const int &a,const int &b){if (a>b)return a;return b;}
inline int minn(const int &a,const int &b){if (a<b)return a;return b;}
int dfs(int x,int s){
	int i,j;
	if (!x){
		if (s>ans){ans=s;return 1;}
		return 0;
	}
	for(i=0;i<x;i++){
		if (x+s-i<=ans)return 0;
		int y=q[s][i];
		if (s+f[y]<=ans)return 0;
		int cnt=0;
		for(j=i+1;j<x;j++)if (way[y][q[s][j]]){
			q[s+1][cnt++]=q[s][j];
		}
		if (dfs(cnt,s+1))return 1;
	}
	return 0;
}
int main(){
	scanf("%d",&n);
	while (scanf("%d%d",&a,&b)!=EOF){way[a-1][b-1]=way[b-1][a-1]=1;}
	for(i=n-1;i>-1;i--){
		int sum=0;
		for(j=i+1;j<n;j++)if (way[i][j])q[1][sum++]=j;
		dfs(sum,1);
		f[i]=ans;
	}
	printf("%d",ans);
	return 0;
}

就这样了……1A

Category: BZOJ | Tags: | Read Count: 1130

[回复]

seo service london 说:
2023年12月31日 22:13

Thanks, first-rate percentage. I simply stumbled upon your weblog and wanted to say that i have absolutely loved analyzing your blog posts. Any way i'll be subscribing in your feed and that i hope you publish again quickly. Big thank you for the beneficial data. Within the especially recent past. The enjoy turned into surely astounding. On the off threat that lone i've the opportunity

[回复]

토블리보증업체 说:
2024年1月03日 14:25

This kind of looks like it's surely exceptional. These kind of small facts are developed employing big selection involving requirements know-how. My spouse and i like the thought plenty.

[回复]

솔카지노도메인 说:
2024年1月03日 14:53

You actually make it look so easy with your performance but I find this matter to be actually something which I think I would never comprehend. It seems too complicated and extremely broad for me. I'm looking forward for your next post, I’ll try to get the hang of it!

[回复]

베팅룸벳 도메인 说:
2024年1月03日 15:07

This excellent looks absolutely appropriate. Every one of moderate information are ready by using large number associated with encounter useful understanding. I am eager this once again greatly.

[回复]

토토배너순위 说:
2024年1月03日 15:25

Hi there! Someone in my Myspace group shared this site with us so I came to give it a look. I’m definitely loving the information. I’m bookmarking and will be tweeting this to my followers! Outstanding blog and wonderful style and design.

[回复]

메이저놀이터 说:
2024年1月03日 15:37

This is exactly what I was looking for. Your post addressed all my queries, and I appreciate the references you included. It's evident that you've done your research. Kudos!

[回复]

안전놀이터추천 说:
2024年1月03日 15:44

I am overwhelmed by your post with such a nice topic. Usually I visit your blogs and get updated through the information you include but today’s blog would be the most appreciable. Well done

[回复]

먹튀검증사이트 说:
2024年1月03日 16:40

Great post! I really enjoyed reading your article. The insights you provided are valuable, and I appreciate the effort you put into explaining the topic thoroughly.

[回复]

엔트리파워볼 说:
2024年1月03日 16:57

EcoDailyLife is your ultimate destination for all things eco-friendly and sustainable living. Explore a wealth of informati. Start making a positive impact on the planet one click at a time with EcoDailyLife.

[回复]

메이저놀이터 说:
2024年1月03日 17:12

It was a very good post indeed. I thoroughly enjoyed reading it in my lunch time. Will surely come and visit this blog more often. Thanks for sharing.

[回复]

우리카지노주소 说:
2024年1月03日 17:21

It was a very good post indeed. I thoroughly enjoyed reading it in my lunch time. Will surely come and visit this blog more often. Thanks for sharing.

[回复]

안전토토사이트 说:
2024年1月03日 17:25

We Provide Today Bhutan Teer Result Live, Bhutan Teer Result, All Teer Result, Bhutan Teer Common Number Every Day 100% Working On

[回复]

먹튀검증 说:
2024年1月03日 17:38

I couldn't agree more with your perspective. Your blog always delivers high-quality content, and this post is no exception. Keep up the fantastic work!

[回复]

단폴배팅사이트가입 说:
2024年1月03日 18:02

hey there, just wanted to tell you that the feed on your site is broken. I was trying to add it to my rss list but it couldn’t work. I had a similar issue on my blog, it wouldn’t work a week and then somehow it just worked! I guess these issues fix thereself sometimes, lol. but I thought to inform you. Take care!.

[回复]

토토일보인증업체 说:
2024年1月03日 18:26

Female Escorts: offer a range of services to their clients, from companionship and intimacy to providing sexual gratification. These ladies come from different backgrounds and can cater to the specific needs of their customers.

[回复]

안전놀이터 说:
2024年1月03日 18:32

The old way of doing things is to try to make your product 10x better than the competition. The new way of doing things is to make your experience 10x lighter than the competition's

[回复]

토토사이트추천 说:
2024年1月03日 18:53

I am speechless. This is a very good blog and very attractive too. Nice work! That’s now not in reality so much coming from an beginner publisher like me, but it’s all I may say after diving into your posts. Nice grammar and vocabulary. Now not like other blogs. You in point of fact recognise what you?re talking approximately too. Such a lot that you made me need to discover more. Your weblog has transform a stepping stone for me, my friend.

[回复]

샌즈카지노회원가입 说:
2024年1月03日 20:10

This kind of looks like it's surely exceptional. These kind of small facts are developed employing big selection involving requirements know-how. My spouse and i like the thought plenty.

[回复]

동행복권파워볼 说:
2024年1月03日 20:17

It's similarly a fantastic write-up i usually certainly appreciated analyzing. It isn't always day-to-day i usually create the chance to find out something.

[回复]

온라인카지노추천 说:
2024年1月03日 20:29

[回复]

토토사이트실험실 说:
2024年1月03日 20:43

It truly is moreover a great write-up which i undoubtedly relished reviewing. It may not be specifically day-to-day which i build an opportunity to get whatever.

[回复]

먹튀없는사이트 说:
2024年1月03日 20:57

That can feel totally proper. Each one of more compact factors have been developed by means of several document schooling. I enjoy the application form lots.

[回复]

먹튀검증커뮤니티 说:
2024年1月03日 21:28

This really is in addition a reasonably very good short article we surely much-loved inspecting. Not really daily which in turn take advantage of the possibilities to identify a product or service.

[回复]

소울 카지노 说:
2024年1月03日 21:35

This excellent looks absolutely appropriate. Every one of moderate information are ready by using large number associated with encounter useful understanding. I am eager this once again greatly.

[回复]

스포츠 중계 说:
2024年1月03日 21:46

Selamat datang di situs kantorbola , agent judi slot gacor terbaik dengan RTP diatas 98% , segera daftar di situs kantor bola untuk mendapatkan bonus deposit harian 100 ribu dan bonus rollingan 1%.

[回复]

사설토토 说:
2024年1月03日 21:56

Selamat datang di situs kantorbola , agent judi slot gacor terbaik dengan RTP diatas 98% , segera daftar di situs kantor bola untuk mendapatkan bonus deposit harian 100 ribu dan bonus rollingan 1%.

[回复]

안전놀이터 说:
2024年1月03日 22:12

Its a great pleasure reading your post.Its full of information I am looking for and I love to post a comment that "The content of your post is awesome" Great work

[回复]

토토사이트추천 说:
2024年1月03日 22:21

[回复]

룰렛사이트 说:
2024年1月03日 22:35

I love how you present your ideas. Your writing is clear, concise, and engaging. The examples you provided make it easy to relate to the topic. I'll definitely be coming back for more.

[回复]

먹튀제보 说:
2024年1月03日 22:51

You understand your projects stand out of the crowd. There is something unique about them. It seems to me all of them are brilliant.

[回复]

단폴토토사이트가입 说:
2024年1月03日 22:56

Thank you for sharing your expertise. Your knowledge on this subject is evident, and I learned a lot from reading your post. Looking forward to more enlightening content from you.

[回复]

토토마스터즈역할 说:
2024年1月03日 23:14

The old way of doing things is to try to make your product 10x better than the competition. The new way of doing things is to make your experience 10x lighter than the competition's

[回复]

먹튀사냥꾼가입 说:
2024年1月03日 23:28

Great Share! Aw, this was a really nice post. In idea I would like to put in writing like this additionally – taking time and actual effort to make a very good article but what can I say I procrastinate alot and by no means seem to get something done.

[回复]

안전사이트 说:
2024年1月03日 23:33

I am fascinated this informative article. There are so many things mentioned here I had never thought of before. You have made me realize there is more than one way to think about these things.

[回复]

먹튀검증업체 说:
2024年1月03日 23:48

Paid phone search services usually go with access to unlimited lookups, discounted background and cell phone reports, and an advanced People Search. You can use the peop search application to find old classmates, long lost relatives, or former co-workers.

[回复]

먹튀검증사이트 说:
2024年1月03日 23:55

Stunning! Such an astonishing and accommodating post this is. I super love it. It's so great thus amazing. I am simply stunned. I trust that you keep on doing your work like this later on moreover.

[回复]

먹튀검증 说:
2024年1月20日 14:34

Hey, I am so thrilled I found your blog, I am here now and could just like to say thank for a tremendous post and all round interesting website. Please do keep up the great work. I cannot be without visiting your blog again and again

[回复]

카지노사이트 说:
2024年1月20日 15:36

definitely enjoying every little bit of it. It is a great website and nice share. I want to thank you. Good job! You guys do a great blog, and have some great contents. Keep up the good work

[回复]

카지노 说:
2024年1月20日 16:06

Thanks so much for the blog post.Really thank you! Much obliged

[回复]

슬롯커뮤니티 说:
2024年1月20日 16:52

I must say this video is a very creative and wonderful explanation. Thank you for taking the time to share it.

[回复]

카지노사이트 说:
2024年1月20日 17:08

That is the reason consentrate on you will need to unique placement of feet some time before authoring. Will likely be doable to help far more suitable writing in this fashion

[回复]

머니맨 说:
2024年1月20日 17:40

It's always exciting to read articles from other writers and practice something from their web sites.

[回复]

바카라 사이트 说:
2024年1月20日 18:18

That is the reason consentrate on you will need to unique placement of feet some time before authoring. Will likely be doable to help far more suitable writing in this fashion

[回复]

온라인카지노 说:
2024年1月20日 19:12

Excellent article. Very interesting to read. I really love to read such a nice article. Thanks!

[回复]

먹튀검증 说:
2024年1月20日 19:51

You got a very fantastic website, Gladiolus

[回复]

슬롯사이트 说:
2024年1月20日 20:31

Admiring the time and effort you put into your blog and detailed information you offer!

[回复]

industrial outdoor s 说:
2024年1月20日 21:03

It proved to be Very helpful to me and I am sure to all the commentators here!

[回复]

카지노사이트 说:
2024年1月21日 13:27

You have a good point here!I totally agree with what you have said!!Thanks for sharing your views...hope more people will read this article!!!

[回复]

소액결제현금화 说:
2024年1月21日 13:58

Great survey, I'm sure you're getting a great response.

[回复]

스포츠무료중계 说:
2024年1月21日 15:45

Admiring the time and effort you put into your blog and detailed information you offer!..

[回复]

카지노커뮤니티 说:
2024年1月21日 16:30

"These are truly fantastic ideas in concerning blogging.

You have touched some nice points here. Any way keep up wrinting."

[回复]

jnanabhumiap.in 说:
2024年1月26日 09:57

JNANABHUMI AP provides all the latest educational updates and many more. The main concept or our aim behind this website has been the will to provide resources with full information on each topic which can be accessed through the Internet. To ensure that every reader gets what is important and worthy about the topic they search and link to hear from us. jnanabhumiap.in Jnanabhumi AP is a startup by passionate webmasters and bloggers who are passionate about providing engaging content that is accurate, interesting, and worthy to read.

[回复]

하노이 유흥 说:
2024年1月26日 12:17

하노이 꼭 가봐야 할 베스트 업소 추천 안내 및 예약, 하노이 밤문화 에 대해서 정리해 드립니다. 하노이 가라오케, 하노이 마사지, 하노이 풍선바, 하노이 밤문화를 제대로 즐기시기 바랍니다. 하노이 밤문화 베스트 업소 요약 베스트 업소 추천 및 정리.

[回复]

카지노사이트 说:
2024年1月26日 12:25

카지노사이트 바카라사이트 우리카지노 카지노는 바카라, 블랙잭, 룰렛 및 슬롯 등 다양한 게임을 즐기실 수 있는 공간입니다. 게임에서 승리하면 큰 환호와 함께 많은 당첨금을 받을 수 있고, 패배하면 아쉬움과 실망을 느끼게 됩니다.

[回复]

먹튀사이트 说:
2024年1月29日 11:33

No.1 먹튀검증 사이트, 먹튀사이트, 검증사이트, 토토사이트, 안전사이트, 메이저사이트, 안전놀이터 정보를 제공하고 있습니다. 먹튀해방으로 여러분들의 자산을 지켜 드리겠습니다. 먹튀검증 전문 커뮤니티 먹튀클린만 믿으세요!!

[回复]

베트남 유흥 说:
2024年1月29日 11:38

베트남 남성전용 커뮤니티❣️ 베트남 하이에나 에서 베트남 밤문화를 추천하여 드립니다. 베트남 가라오케, 베트남 VIP마사지, 베트남 이발관, 베트남 황제투어 남자라면 꼭 한번은 경험 해 봐야할 화끈한 밤문화로 모시겠습니다.

[回复]

코인지갑개발 说:
2024年4月24日 12:22

https://xn--539awa204jj6kpxc0yl.kr/
블록체인개발 코인지갑개발 IT컨설팅 메스브레인팀이 항상 당신을 도울 준비가 되어 있습니다. 우리는 마음으로 가치를 창조한다는 철학을 바탕으로 일하며, 들인 노력과 시간에 부흥하는 가치만을 받습니다. 고객이 만족하지 않으면 기꺼이 환불해 드립니다.

sxczf's Blog

AFO