부족 수비대 문제
원시 부락의 주민 들 은 자원 을 쟁탈 하기 위해 자주 충돌 이 발생 했다.거의 모든 주민 에 게 원수 가 있다.추장 은 부족 수비 대 를 조직 하기 위해 희망 한다.
부족 주민 중 가장 많은 주민 을 뽑 아 입대 시 키 고 팀 중 두 명 이 원수 가 아니 라 는 것 을 보증한다.
프로 그래 밍 작업:
주어진 주민 간 의 원수 관계 에 따라 부족 수비대 의 최 적 방안 을 프로 그래 밍 해 냈 다.
데이터 입력:
제1 행 2 개 정수 n, m 는 부락 중의 주민 개 수 를 나타 내 고 주민 중 m 개의 원수 관계 가 있다.주민 번호 1, 2, n.다음 m 줄, 줄 당 2
개 정수 u, v 는 주민 u 와 v 가 원수 임 을 나타 낸다.
입력 실례:
7 10 1 2 1 4 2 4 2 3 2 5 2 6 3 5 3 6 4 5 5 6
출력 실례: 3
구현 코드:
#include <iostream>
#include <vector>
#include <string>
using namespace std;
int totalpeople = 100,best=0,totalrelation; // 100 , 100
vector<int>markvisit(totalpeople+1,0); // (1: ,0: )
vector<vector<int> > relation(totalpeople+1 ,vector<int>(totalpeople+1,0)); //
void select(int start,int wantselect,int selected) // select( , , )
{
if(selected+totalpeople-wantselect<best)
{
return;
}
if(selected==wantselect) // wantselect ,
{
vector<int>tmpselected;
for(int i=1;i<=totalpeople;i++)
{
if(markvisit[i]==1)
{
tmpselected.push_back(i);
}
}
bool mark=false;
for(int j=0;j<tmpselected.size();j++)
{
for(int k=j+1;k<tmpselected.size();k++)
{
if(relation[tmpselected[j]][tmpselected[k]]==1)
{
mark=true;
break;
}
}
if(mark)
{
break;
}
}
if(!mark)
{
if(selected>best) // ,
{
best=selected;
}
}
tmpselected.clear();
}
for(int j=start; j<=totalpeople; j++) // ,
{
if(markvisit[j]==0) // ,
{
markvisit[j]=1;
select(j+1,wantselect,selected+1); //
markvisit[j]=0;
}
}
}
int main()
{
int tmpx,tmpy;
cin>>totalpeople>>totalrelation;
for(int i=1; i<=totalrelation; i++)
{
cin>>tmpx>>tmpy;
relation[tmpx][tmpy]=1;
relation[tmpy][tmpx]=1;
}
for(int j=1; j<=totalpeople; j++)
{
select(1,j,0);
}
cout << best << endl;
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【Codility Lesson3】FrogJmpA small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.