程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> Codeforces Round #318-(B. Bear and Three Musketeers)

Codeforces Round #318-(B. Bear and Three Musketeers)

編輯:C++入門知識

Codeforces Round #318-(B. Bear and Three Musketeers)


這道題做的時候還剩下30多分鐘了,於是有點慌。。。果然心理素質還是有待提高,這麼水的題都沒有過):導致又掉rating了。。。

題意:

現在給你n個人,m個詢問,然後接下來m行告訴你a與b是相互認識的,但是這個認識不能夠相互傳遞,也就是說a認識b,b認識c,但是a並不認識c。

然後問你是否能夠在這n個人中選取3個人,使得它們認識其他人的總數最少,並且這三個人要相互認識(也就是a-b,b-c,c-a),如果不存在則輸出-1

思路:

1)暴力,枚舉3個人(我只能說cf的服務器好,竟然這都能夠跑過去)==

2)也是暴力,但是小處理一下,把每個人認識的都相當於用鄰接表的形式存下來。

1)

 

#include
#include
#include
#include
#include
#include
using namespace std;
#define inf 99999999
#define maxn 4010
vector G[maxn];
int num[maxn];
int e[maxn][maxn];
int main(){
	int n,m;
	scanf(%d%d,&n,&m);
	for(int i=1;i<=m;i++){
		int a,b;
		scanf(%d%d,&a,&b);
		e[a][b]=e[b][a]=1;
		num[a]++;
		num[b]++;
		G[a].push_back(b);
		G[b].push_back(a);
	}
	int lmin=inf;
	for(int i=1;i<=n;i++){
		int nn=0,a,b,c;
		for(int j=0;j

 

 

2)

 

#include
#include
#include
#include
#include
#include
using namespace std;
#define inf 99999999
#define maxn 4010
vector G[maxn];
int vis[maxn][maxn];
int a[maxn],b[maxn];
int main(){
	int n,m;
	scanf(%d%d,&n,&m);
	for(int i=1;i<=m;i++){
		scanf(%d%d,&a[i],&b[i]);
		G[a[i]].push_back(b[i]);
		G[b[i]].push_back(a[i]);
		vis[a[i]][b[i]]=vis[b[i]][a[i]]=1;
	}
	int lmax=inf;
	for(int i=1;i<=m;i++){
		int u=a[i],v=b[i];
		if(G[u].size()>=2&&G[v].size()>=2){
			for(int j=0;j

 

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved