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;
}