题目大意
给出一个n个点的竞赛图，现从中钦定 $k$ 个点，保证将这 $k$ 个点移除后，剩余的图将不存在环。
求出在不移除任何一个钦定的点的情况下，移除一些点使图中没有环的最小所需移除的点数。
如果这个数目大于等于 $k$ 或不存在，输出 impossible。
$2 leq k,n leq 1000$
题解
首先钦定的不能删的$k$个点如果成环了显然就没救了。
也就是说，题目保证了钦定的点和没钦定的点构成的生成子图都是DAG。
为了方便描述，接下来把钦定的点称为白点，没钦定的点称为黑点。
首先给出一个关于竞赛图的引理:
对于一个点数为 $n$ 的强联通竞赛图，一定存在大小为$i$的环，其中$3 leq i leq n$。
一发简单证明：
$n=3$显然成立，假设$n>3$，随意删除图上的一个点$x$，设剩下的强联通分量分别为$A_1,A_2 ,cdots, A_n$。
由于原图强联通，那么这些强连通分量显然不会因为删了一个点就不相连，于是这些强联通分量显然是联通的。于是令这些强连通分量的顺序满足若$i<j$，存在$A_i->A_j$的边。
同时由于此图强联通，那么显然存在$x->A_1$以及$A_n->x$。
于是就有了环:$x->A_1->A_2-> cdots -> A_n -> x$，长度为$n$。
由于删点后剩下的这些强连通分量同样可以这么构造，那么得证、
有了这个引理，目标就变成了删除所有的三元环，因为任意长度大于$3$的环，由于是强连通分量，始终包含三元环。
可以发现，本质不同的三元环只有两种:两黑一白，两白一黑。
两白一黑的话，把唯一的黑的删掉即可。但两黑一白就需要选择删哪个黑划算。
于是考虑搞出黑点和白点的拓扑序，黑点设为$X$，白点设为$Y$。
可以发现，拓扑序中对于任意$i<j$，存在边$i->j$。
不难发现，将$X$扫一遍，对于每个黑点$x$，若存在$i<j,x->i,j->x$，那么找到了一个两白一黑环，删去这样的黑点。
于是现在对于每个剩下来的黑点，满足在$Y$的拓扑序上，所有$x->y$边出现在$y->x$边之后。
那么出现一个两黑一白的条件是，对于$X$中的点，满足$i<j$时，存在节点$y in Y$，满足 $ y -> x_i , x_j -> y $。
于是记录一下对于每个黑点$x_i$的$x_i->y$边最早出现的位置$f_i$，那么两个黑点不相交的条件为$i < j , f_i leq f_j$
做个最长不上升子序列，剩下来的就是最多能保留的点。
于是做完了~
代码:
#include<cstdio>
#include<vector>
using namespace std;
inline int read()
{
int x=0;char ch=getchar();
while(ch<'0' || '9'<ch)ch=getchar();
while('0'<=ch && ch<='9')x=x*10+(ch^48),ch=getchar();
return x;
}
inline void chkmax(int &a,int b){if(a<b)a=b;}
const int N=2009;
int n,k,ans;
int a[N][N],idx[N];
int must[N],idy[N];
int id[N],f[N],top;
vector<int> x,y;
inline bool topsort(const vector<int> &p,int *q)
{
static int ind[N],r;
for(int i=0;i<p.size();i++)
for(int j=0;j<p.size();j++)
if(a[p[i]][p[j]])
ind[p[j]]++;
for(int i=r=0;i<p.size();i++)
if(!ind[p[i]])
q[++r]=p[i];
for(int l=1,u=q[l];l<=r;u=q[++l])
for(int i=0;i<p.size();i++)
if(a[u][p[i]] && !(--ind[p[i]]))
q[++r]=p[i];
return r==p.size();
}
inline int lis(int *a,int n)
{
static int f[N],ret;
f[0]=ret=0;a[0]=-1;
for(int i=1;i<=n;i++)
{
f[i]=0;
for(int j=0;j<i;j++)
if(a[j]<=a[i])
chkmax(f[i],f[j]);
chkmax(ret,++f[i]);
}
return ret;
}
int main()
{
n=read();k=read();
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
a[i][j]=read();
for(int i=1;i<=k;i++)
must[read()]=1;
for(int i=1;i<=n;i++)
if(!must[i])
x.push_back(i);
else
y.push_back(i);
topsort(x,idx);
if(!topsort(y,idy))
return puts("impossible"),0;
for(int i=1;i<=x.size();i++)
{
for(int j=2;j<=y.size();j++)
if(a[idy[j]][idx[i]] && a[idx[i]][idy[j-1]])
{
ans++;
goto hell;
}
id[++top]=idx[i];
for(int j=1;j<=y.size() && !f[top];j++)
if(a[id[top]][idy[j]])
f[top]=j;
hell:;
}
ans+=top-lis(f,top);
if(ans<k)printf("%d
",ans);
else puts("impossible");
return 0;
}