[2018HN省队集训D9T1] circle
题意
给定一个 $n$ 个点的竞赛图并在其中钦定了 $k$ 个点, 数据保证删去钦定的 $k$ 个点后这个图没有环. 问在不删去钦定的这 $k$ 个点的情况下最少要删几个点让原图没有环. 如果不存在答案小于 $k$ 的解则输出 impossible.
$n,k\le2000$.
题解
好像这篇草稿鸽的时间有点久qaq
首先一个显然的性质是无环的竞赛图一定是一个全序集.
其次是如果钦定的点不是全序集那么必定无解.
无解判掉之后所有的点就被分成了两个全序集合(数据保证剩下的点无环). 我们枚举剩下的点看它能不能合法插入被钦定的全序集中. 对于能合法插入的点, 一定会有一个唯一的插入位置. 显然我们必须让这些点的插入位置递增(因为要满足两个全序关系). 于是我们按照全序顺序把所有能插入的点的插入位置求出来, 然后在上面求一个最长上升子序列就好了.
时间复杂度 $O(n^2)$.
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
|
#include <bits/stdc++.h>
const int MAXN=2010;
int n;
int k;
int val[MAXN];
int cnt[MAXN];
bool blk[MAXN];
int m[MAXN][MAXN];
std::vector<int> s;
std::vector<int> r;
void Fail();
int ReadInt();
int main(){
n=ReadInt();
k=ReadInt();
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
m[i][j]=ReadInt();
for(int i=0;i<k;i++){
s.push_back(ReadInt());
blk[*s.rbegin()]=true;
}
for(int i=1;i<=n;i++)
if(!blk[i])
r.push_back(i);
auto cmp=[](int a,int b){return bool(m[a][b]);};
std::sort(r.begin(),r.end(),cmp);
std::stable_sort(s.begin(),s.end(),cmp);
for(int i=0;i<k;i++)
for(int j=i+1;j<k;j++)
if(!cmp(s[i],s[j]))
Fail();
for(auto i:r){
bool flag=true;
for(auto j:s){
if((!flag)&&cmp(j,i)){
val[i]=-1;
break;
}
flag&=cmp(j,i);
if(flag)
++val[i];
}
}
int ans=0;
for(auto i:r){
if(val[i]==-1)
continue;
cnt[i]=1;
for(auto j:r){
if(i==j)
break;
if(val[j]!=-1&&val[j]<=val[i])
cnt[i]=std::max(cnt[i],cnt[j]+1);
}
ans=std::max(ans,cnt[i]);
}
ans=r.size()-ans;
if(ans<k)
printf("%d\n",ans);
else
Fail();
return 0;
}
void Fail(){
puts("impossible");
exit(0);
}
int ReadInt(){
int x=0;
register char ch=getchar();
while(!isdigit(ch))
ch=getchar();
while(isdigit(ch)){
x=x*10+ch-'0';
ch=getchar();
}
return x;
}
|
