부족 수비대 문제

2546 단어 알고리즘cc++
부족 수비대 문제 설명:
원시 부락의 주민 들 은 자원 을 쟁탈 하기 위해 자주 충돌 이 발생 했다.거의 모든 주민 에 게 원수 가 있다.추장 은 부족 수비 대 를 조직 하기 위해 희망 한다.
부족 주민 중 가장 많은 주민 을 뽑 아 입대 시 키 고 팀 중 두 명 이 원수 가 아니 라 는 것 을 보증한다.
프로 그래 밍 작업:
주어진 주민 간 의 원수 관계 에 따라 부족 수비대 의 최 적 방안 을 프로 그래 밍 해 냈 다.
데이터 입력:
제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;
}


좋은 웹페이지 즐겨찾기