题目描述

$xxxxxyt$学姐经常一个人在家,难免会感到寂寞,于是学姐养了n只可爱的宠物。

比如皮皮虾、大蟒蛇、藏狐、安康鱼…但即便如此学姐还是感到无聊。

突然有一天,学姐想到了让宠物们互相对战的消遣方法(请不要给动物保护协会打电话!)。

学姐让宠物们两两进行对战,$\frac{n\times(n-1)}{2}$场对战后,学姐得到了一张相生相克图,

然后又根据自己的喜好,把宠物们分成了一队与二队。

就在队伍分好后,学姐的强迫症又犯了,她希望自己的两支队伍都满足这样一个性质:

存在某种排列,使得排在后面的宠物能够击败排在前面的所有宠物。

但学姐的懒惰大家都是知道的,所以她找到了你,希望你能告诉她这两支队伍是否均满足要

求,如果是,她还希望你告诉她最多可以从二队中抽出多少只宠物放在一队,使得两支队伍

仍然满足要求。

努力解决问题吧,而$xxxxxyt$学姐,瘫躺。

输入格式

第一行输入两个数字$n$和$m$,分别表示学姐有$n$只宠物,其中被分到一队的宠物有$m$只。

接下来$n$行每行$n$个数字,$a_{i,j}$表示第$i$只宠物是否能战胜第$j$只宠物,保证$a_{i,i}=0$且$a_{i,j}=!a_{j,i}$。

接下来一行$m$个数字,表示有哪些宠物被分到了一队。

输出格式

如果两支队伍均不能让$xxxxxyt$满意,则输出$“NO”$;

否则输出$“YES”$,并输出一个最大的$k$,使得从二队中非任意地抽出$k$只宠物放入一队后,两支队伍仍然满足条件。

详细格式见样例输出。

样例输入

$Case1$

3 2
0 1 1
0 0 1
0 0 0
3 1

$Case2$

4 3
0 1 0 1
0 0 1 1
1 0 0 1
0 0 0 0
1 2 3

$Case3$

4 2
0 1 0 1
0 0 1 1
1 0 0 1
0 0 0 0
1 2

样例输出

$Case1$

YES 1

$Case2$

NO

$Case3$

YES 1

数据范围

宠物们的实力是相对的,也就是可能会出现$A$战胜$B$,$B$战胜$C$,$C$又战胜$A$的情况。

$100\%$的数据$1\leq m<n\leq1000$

$Subtask1$

如果一个队伍合法,一定不会出现$A$赢$B$,$B$赢$C$,$C$又赢$A$的情况。

所有当我们将战胜关系连边后,有向图无环且连通,则队伍是合法的。

于是我们想到了拓扑排序。

由胜方向败方连边,拓扑序中排在前面的动物一定可以战胜所有排在后面的动物。

$Subtask2$

考虑从$B$对中抽尽量多的动物到$A$队。

首先,在一个序列合法的情况下:

抽出其中一个动物后序列依旧合法。

插入一个动物后,如果该动物赢所有后面的动物,败于所有前面的动物,则序列依旧合法。

其次,在插入的多个动物中,它们相对位置的先后要满足合法性。

所以,求出$B$队拓扑序中的点在$A$中能插入的位置。

位置数组的最长不下降子序列的长度即为答案。

代码

#include<bits/stdc++.h>
#define maxn 1005
using namespace std;
inline int read(){
    char ch=getchar();int s=0,w=1;
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){s=(s<<1)+(s<<3)+ch-48;ch=getchar();}
    return s*w;
}
int n,m,cnt1,cnt2;
int vis[maxn];
int pos[maxn];
int beat[maxn][maxn];
vector<int> g[maxn];
int indu[maxn];
queue<int> q;
bool flag;
int one[maxn],two[maxn];
int toposort(int pos){
    for(int i=1;i<=n;i++){
        if(vis[i]==pos&&!indu[i]){
            q.push(i);
        }
    }
    int cnt=0;
    while(!q.empty()){
        cnt++;
        int x=q.front();q.pop();
        (pos==1?one[cnt]:two[cnt])=x;
        for(int i=0;i<g[x].size();i++){
            int y=g[x][i];
            indu[y]--;
            if(indu[y]==0) q.push(y);
        }
    }
    return cnt;
}
int main(){
    freopen("pets.in","r",stdin);
    freopen("pets.out","w",stdout);
    n=read();m=read();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            beat[i][j]=read();
        }
    }
    int xx;
    cnt1=m; cnt2=n-m;
    for(int i=1;i<=cnt1;i++){
        xx=read(); vis[xx]=1;
    }
    //一队 
    for(int i=1;i<=n;i++){
        if(!vis[i]) continue;
        for(int j=1;j<=n;j++){
            if(!vis[j]) continue;
            if(beat[i][j]){
                indu[i]++;
                g[j].push_back(i);    
            }
        }
    }
    if(toposort(1)!=cnt1){
        puts("NO");
        return 0;
    } 
    //二队 
    for(int i=1;i<=n;i++){
        if(vis[i]) continue;
        for(int j=1;j<=n;j++){
            if(vis[j]) continue;
            if(beat[i][j]){
                indu[i]++;
                g[j].push_back(i);    
            }
        }
    }
    if(toposort(0)!=cnt2){
        puts("NO");
        return 0;
    } 
    printf("YES ");
    for(int i=1;i<=cnt2;i++){
        int x=two[i];
        int k=1;
        while(beat[x][one[k]]&&k<=cnt1) k++;
        pos[i]=k;
        while(beat[one[k]][x]&&k<=cnt1) k++;
        if(k!=cnt1+1) pos[i]=0;
    }
    int f[maxn];
    for(int i=1;i<=cnt2;i++){
        f[i]=1;
        if(!pos[i]) continue;
        for(int j=i-1;j>=1;j--){
            if(pos[i]>=pos[j]&&pos[j]) f[i]=max(f[i],f[j]+1);
        }
    }
    int ans=0;
    for(int i=1;i<=cnt2;i++){
        ans=max(ans,f[i]);
    }
    printf("%d\n",ans);
    return 0;
}