BZOJ 1854[Scoi 2010]游戏题解と分析

1854:[Scoi 2010]ゲーム
Time Limit: 5 Sec  
Memory Limit: 162 MB
Submit: 1488  
Solved: 498
[ Submit][ Status]
Description
lxhgwwは最近1種のゲームに夢中になって、ゲームの中で、彼は多くの装備を持っていて、それぞれの装備はすべて2つの属性があって、これらの属性の値は[11000]の間の数で表します.ある装備を使用すると、その装備の属性の1つしか使用できません.また、装備ごとに最大1回しか使用できません.ゲームは最後まで行われ、lxhgwwは究極のbossに遭遇した.この究極のbossは奇妙で、彼の装備を攻撃するために使用される属性値は1から連続的に増加して攻撃しなければ、bossにダメージを与えることができない.つまり最初はlxhgwwは,ある属性値が1の装備攻撃bossしか使えず,ある属性値が2の装備攻撃bossしか使えず,ある属性値が3の装備攻撃bossしか使えない…ということになる.今lxhgwwは彼が最大何回bossを連続的に攻撃することができることを知りたいですか?
Input
入力された最初の行は整数Nであり、lxhgwwがN種類の装備を持っていることを示し、次のN種類の装備の説明であり、行ごとに2つの数字があり、i種類の装備の2つの属性値を表す.
Output
lxhgwwが最大連続攻撃できる回数を示す1行を出力します.
Sample Input
3 1 2 3 2 4 5
Sample Output
2
HINT
【データ範囲】30%のデータに対して、N<=1000が100%のデータに対して、N<=1000000が保証される
Source
Day1
 
原題接続:http://www.lydsy.com/JudgeOnline/problem.php?id=1854
【分析】:この問題は二分図マッチングで、BZOJ 1191[HNOI 2006]スーパーヒーローHeroと同様に、挑戦BOSSは次から次へと続き、中断できない場合は、マッチングできない場合は出力解答を終了する.装備でターンを合わせる.ただし、N≦1000000のため、図面作成時に直接2次元を開くことができず、隣接チェーンテーブルを作成する必要があります.また、マッチング後のvisit初期化のたびにmemsetは使用できません.そうしないとタイムアウトします.c++のSTL-bitsetは同じ役割を果たすことができる.
【コード】:

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#include<iostream>
#include<bitset>
using namespace std;
#define MAX 1000001
struct MAP1{int next,to;};
MAP1 a[2*MAX];
int M,q[2*MAX],tot=1,N;
int P[MAX],ans=0,max1=0;
bitset<MAX> visit;
void add_point(int A,int B)
{
	a[tot].to=B;
	a[tot].next=q[A];
	q[A]=tot++;
}
bool work(int now)
{
	for(int i=q[now];i;i=a[i].next)
	{
		  if(!visit[a[i].to])
		  {
		  	   visit[a[i].to]=1;
		  	   if(!P[a[i].to] || work(P[a[i].to]))
		  	   {
		  	   	      P[a[i].to]=now;
		  	   	      return true;
			   }
		  }
	}
	return false;
}
int main()
{
	//freopen("game.in","r",stdin);
	//freopen("game.out","w",stdout);
	memset(a,0,sizeof(a));
	memset(P,0,sizeof(P));
	scanf("%d",&N);
	for(int i=1;i<=N;i++)
	{
		  int A,B;
	      scanf("%d%d",&A,&B);
	      max1=max(A,max1);
	      max1=max(B,max1);
	      add_point(A,i);
	      add_point(B,i);
	}
	for(int i=1;i<=max1;i++)
	{
		  //memset(visit,false,sizeof(visit));
		  visit.reset();
		  if(work(i))   ans++;
		  else break;
    }
    printf("%d
",ans);
    //system("pause");
    return 0;
}

転載して出典を明記する:http://blog.csdn.net/u011400953