낙곡P1640 [SCOI2010] 연속 공격 게임(2점도 일치)
문제풀이의 방향
모든 공격력에서 무기로 연결하여 이분도를 형성한 후 매거 공격력 1...10000, 일치하면 계속, 그렇지 않으면 출력 프로그램이 끝납니다.
참고:
모든 공격력을 일일이 열거할 때memset으로 비우면vis수 그룹이 시간을 초과합니다. (TLE 네 개 점) 그래서 우리는 표시를 한 후에 종료하기 전에 단일 비웁니다. (코드 참조)
AC 코드
1 #include
2 #include
3 #include
4 using namespace std;
5 const int maxn=1000005;
6 int cnt,n,p[10005],vis[maxn],ok[maxn];
7 struct edge{
8 int v,next;
9 }e[maxn*2];
10 void insert(int u,int v){
11 cnt++;
12 e[cnt].v=v;
13 e[cnt].next=p[u];
14 p[u]=cnt;
15 }
16 bool work(int u){
17 for(int i=p[u];i!=-1;i=e[i].next){
18 int v=e[i].v;
19 if(vis[v]) continue;
20 vis[v]=1;
21 if(!ok[v]||work(ok[v])){
22 ok[v]=u;
23 vis[v]=0;
24 return true;
25 }
26 vis[v]=0;
27 }
28 return false;
29 }
30 int main()
31 {
32 memset(p,-1,sizeof(p));
33 cin>>n;
34 for(int i=1;i<=n;i++){
35 int u1,u2;
36 scanf("%d%d",&u1,&u2);
37 insert(u1,i);
38 insert(u2,i);
39 }
40 for(int i=1;i<=10001;i++){
41 if(!work(i)){
42 cout<1;
43 return 0;
44 }
45 }
46 return 0;
47 }
//SCOI2010 Day1t2
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.