tyvj 1348 清理内奸
清理内奸
描述 Description
最近FF博士在玩一个游戏“三国杀杀杀”，他扮演一个英明的主公，四处清剿反贼。终于把反贼全部干掉了，可是他的手下还存在着一些内奸
。经过他的观察和研究，终于发现了内奸的重要特征。内奸最重要的工作就是传递情报，所以内奸必须掌握各种加密方法。于是他们对素数有
一种偏好，编号是素数的人全部是内奸。FF博士将指挥忠臣干掉内奸。忠臣和内奸排成一排，第i个人的编号为Bi。杀死内奸会获得一定量经验
，等级为X的忠臣杀死任意等级的内奸会获得X点经验。每个人都有一定的攻击范围，若站在i位置的人攻击范围为k那么他可以杀[i-k,i+k]范围
内的人，但是每个人都只有一次攻击的机会。内奸们并不知道自己的身份已经暴露，不会攻击任何人，只能做待宰的羔羊，FF博士确定了攻击
方案后会在瞬间下令让忠臣行动，内奸会被秒（也就是内奸死亡不会对原来攻击范围造成影响）。
请帮FF博士计算
1、他这次最多能干掉多少内奸呢？
2、在干掉内奸人数最多的情况下，他能获得最多多少经验？
输入格式 Input Format
第一行一个数字n，代表FF博士手下有n个人
第二行n个数，第i个数代表第i个人的编号Bi
3~n+2行，每行2个数x，k分别代表第i个人的等级和攻击范围。
输出格式 Output Format
第一行是FF博士最多能干掉的内奸数量
第二行是FF博士在干掉最多内奸的基础上能获得的最多经验数。
样例输入 Sample Input
7
1 2 3 4 5 6 8
1 1
3 1
4 1
5 2
10 5
1 1
0 100
样例输出 Sample Output
3
7
时间限制 Time Limitation
1S
注释 Hint
样例解释
第2、3、5个人是内奸 (第7个不是，他的编号为8)
1杀2，获得1点经验
4杀3，获得5点经验
6杀5，获得1点经验
数据范围
对于100%的数据
n<=1000
Bi<=10^7
x,k<=100
所有数据不会出现负数。
分析：“这题其实很容易看出来，n个人分成了2个阵营。每个忠臣与他攻击范围内的内奸连一条边。此题第一问就是求二分图的最大匹配。第
二问是个贪心，权值在点上而不是在边上，所以按等级排序，优先满足等级高的忠臣。因为他一旦匹配成功，就不会被换下来。由于最大匹配
数肯定是确定的，所以让等级高的优先匹配并不会影响结果。”即对于二分原图得到的两个图，若两个子图内的元素之间不存在边，那么确定
一个图，另外一个图中的元素任意改变顺序，都不会影响到最大匹配，所以第二问中只要优先满足等级高的忠臣就可以得到正解。
小结：二分图的最大匹配+贪心（排序应该不是问题）
#include <iostream>#include <algorithm>#include <memory.h>using namespace std;const int maxn = 1010;struct person { int pno;//编号 int grade;//等级 int range;//攻击范围 bool isPrime;//编号是否为素数 int cno;};struct node{ int index;//下标 int grade; };person p[maxn];node x[maxn];int n;int white,black;bool cmp(node a,node b){ return a.grade>b.grade;}bool isPrime(int k){ if(k==1) return false; if(k==2) return true; for(int i=2;i*i<=k;i++) { if(k%i==0) return false; } return true;}int adjl[maxn][maxn];int matx[maxn];int maty[maxn];int used[maxn];int match;bool find(int k){ for(int i=1;i<=adjl[k][0];i++) { int j=adjl[k][i]; if(!used[j]) { used[j]=1; if(maty[j]==-1||find(maty[j])) { maty[j]=k; matx[k]=j; return true; } } } return false;}void hungary(){ for(int i=0;i<white;i++) { if(matx[x[i].index]==-1) { memset(used,0,sizeof(used)); if(find(x[i].index)) { match++; //cout<<x[i].index<<endl; } } }}int main(){ cin>>n; for(int i=0;i<n;i++) { cin>>p[i].pno; if(isPrime(p[i].pno)) p[i].isPrime=true; else p[i].isPrime=false; } for(int i=0;i<n;i++) cin>>p[i].grade>>p[i].range; white=black=0; for(int i=0;i<n;i++) { if(p[i].isPrime) p[i].cno=black++; else { p[i].cno=white; x[white].index=white; x[white++].grade=p[i].grade; } } memset(adjl,0,sizeof(adjl)); for(int i=0;i<n;i++) { if(!p[i].isPrime) { for(int j=max(0,i-p[i].range);j<=min(i+p[i].range,n-1);j++) { if(p[j].isPrime) { int r=++adjl[p[i].cno][0]; adjl[p[i].cno][r]=p[j].cno; } } } } /*for(int i=0;i<white;i++) { cout<<i<<": "; for(int j=1;j<=adjl[i][0];j++) { cout<<adjl[i][j]<<" "; } cout<<endl; }*/ sort(x,x+white,cmp); memset(matx,-1,sizeof(matx)); memset(maty,-1,sizeof(maty)); match=0; hungary(); int sum=0; for(int i=0;i<n;i++) { if(!p[i].isPrime) { if(matx[p[i].cno]!=-1) sum+=p[i].grade; } } cout<<match<<endl; cout<<sum<<endl; //system("pause"); return 0;}