낙곡P1640 [SCOI2010] 연속 공격 게임(2점도 일치)

6470 단어
전송문
문제풀이의 방향
모든 공격력에서 무기로 연결하여 이분도를 형성한 후 매거 공격력 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

좋은 웹페이지 즐겨찾기