Description

你玩过call of duty这个游戏吗？这个游戏以诺曼底登陆为背景，假设你是盟军的一员，身在前线去完成许多任务而粉碎纳粹的野心。现在假设有一个任务，德军有很多机枪阵地，火力很猛，如果不把它们摧毁就会对盟军的推进造成很大损失，盟军打算派出一些敢死队员深入阵地把这些机枪阵地炸毁，当然，敢死队员会有很大的生命危险，所以盟军的指挥官希望你能帮他把损失降到最少。

Input

输入数据第一行是一个整数n(1<=n<=200)，代表有多少个机枪阵地需要摧毁。然后接下来n行，每行两个整数xi,yi，代表每个机枪阵地的坐标(0<=xi,yi<=30000)，然后接着一个整数m,跟着有m行，每行两个整数p和q(1<=p,q<=n,p<>q)，代表机枪阵地p和机枪阵地q之间有路相连，敢死队员炸掉一个机枪阵地之后，必须从当前的机枪阵地出发沿着路到达下一个x坐标比当前阵地大的阵地(因为机枪阵地的纵深方向是沿着x坐标递增方向的)，如果不存在这样的阵地，那这名敢死队员就完成任务了。简单来说，一个敢死队员可以空降到任意一个机枪阵地（设为a0）,然后从这个阵地出发按照上面所述可以摧毁一系列机枪阵地(顺序列为a0,a1,a2...ak),而这一系列机枪阵地的x坐标满足（x0 < x1 < x2 < ... < xk）。从安全和效率出发，每个敢死队员可以带任意个炸弹。任意两个敢死队员的路线不能有交点。现在问你怎么安排敢死队员的路线，可以使到用最小数目的敢死队员去完成这个艰巨的任务。

Output

输出一个整数，就是所求的敢死队员的最小数目。

Sample Input

4 25990 5850 8263 2957 1067 22231 4109 4577 3 4 1 2 4 1 3

Sample Output

2

Data Constraint

m<10000

Hint

解释： 上面的例子最少需2个敢死队员，1种方案是：1个摧毁阵地4后再去摧毁阵地2，1个敢死队员摧毁阵地3后去摧毁阵地1。

Solution

最小链覆盖

Code

#include<cstring> #include<cstdio> #include<algorithm> #include<cmath> #define I int #define F(i,a,b) for(I i=a;i<=b;i++) #define Fd(i,a,b) for(I i=a;i>=b;i--) #define mem(a,b) memset(a,b,sizeof a) #define N 204 using namespace std; void R(I &x){ I w=1;x=0;char c=getchar(); while(c<'0'||c>'9'){if(c=='-') w=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} x*=w; } I n,x[N],y[N],m,a[N][N],cnt,bz[N],mt[N]; I dg(I x){ F(i,1,n) if(a[x][i]&&!bz[i]){ bz[i]=1; if(mt[i]==-1||dg(mt[i])){ mt[i]=x; return 1; } } return 0; } I main(){ freopen("Call of duty.in","r",stdin); freopen("Call of duty.out","w",stdout); R(n); F(i,1,n){ R(x[i]),R(y[i]); } R(m); F(i,1,m){ R(x[0]),R(y[0]); if(x[x[0]]>x[y[0]]) a[x[0]][y[0]]=1; if(x[y[0]]>x[x[0]]) a[y[0]][x[0]]=1; } mem(mt,255); F(i,1,n){ mem(bz,0); cnt+=dg(i); } printf("%d\n",n-cnt); return 0; }