图论完结 :)
# 题面
> Codeforces 1344C
点击展开/折叠 题面翻译
有 $n$ 个变量 $x_1,x_2,\dots,x_n$ 以及 $m$ 个不等式关系 $x_{a_i}< x_{b_i}$。
你需要决定 $n$ 个符号 $Q_i$，$Q_i$ 为 $\forall$ 或 $\exists$，使得下式
$$Q_1x_1,Q_2x_2,\dots,Q_nx_n,x_{a_1}< x_{b_1},x_{a_2}< x_{b_2},\dots,x_{a_m}< x_{b_m}$$
值为真。求 $\forall$ 最多可以有多少，并输出 $\forall$ 最多的任意方案。
# 解析
根据对题目的理解，我们发现一个连续的不等式只有下面这一种情况可以满足：
也就是说，前面决定的 $\forall$ 和 $\exists$ 只有第一个可以取 $\forall$。换句话说，对于一个不等式链 $x_{a_1}< x_{a_2}< \dots< x_{a_k}$，只有 $a_i$ 最小的点的前面可以放 $\forall$。
因此，若 $x_u< x_v$，则连有向边 $u\to v$。这样正反建图，求出一个变量相关的所有不等式链。
首先判环，有环则一定无解。
若变量 $x_i$ 是其所在的所有不等式链中 $i$ 最小的，则 $x_i$ 前可以用 $\forall$。在 DAG 上求一个点的所有能够到达的点中最小的，可以用 DP 解决。
所以正反图两遍 DP 就可以 $O(n)$ 解决。
# 源代码
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
|
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
inline int Read(){
register int r=0,c=getchar();
while(c<'0' || '9'<c) c=getchar();
while('0'<=c && c<='9') r=(r<<1)+(r<<3)+(c^'0'),c=getchar();
return r;
}
const int N=2e5+10;
#define cs const int &
struct GRAPH{
int head[N],to[N],nxt[N],ncnt;
void AddEdge(cs u,cs v){
int p=++ncnt;
nxt[p]=head[u],to[p]=v;
head[u]=p;
}
int operator [](cs u){return head[u];}
}Gr,Rev;
int n,m;
bool vis[N],ins[N],cir;
int f[N],rf[N];
char ans[N];
void DFS(cs u){
vis[u]=true,ins[u]=true;
for(int it=Gr[u];it;it=Gr.nxt[it]){
int v=Gr.to[it];
if(!vis[v]) DFS(v);
else cir|=ins[v];
}
ins[u]=false;
}
int DP(cs u){
if(f[u]) return f[u];
f[u]=u;
for(int it=Gr[u];it;it=Gr.nxt[it])
f[u]=min(f[u],DP(Gr.to[it]));
return f[u];
}
int RDP(int u){
if(rf[u]) return rf[u];
rf[u]=u;
for(int it=Rev[u];it;it=Rev.nxt[it])
rf[u]=min(rf[u],RDP(Rev.to[it]));
return rf[u];
}
int main(){
n=Read(),m=Read();
for(int i=1;i<=m;i++){
int u=Read(),v=Read();
Gr.AddEdge(u,v);
Rev.AddEdge(v,u);
}
for(int i=1;i<=n;i++)
if(!vis[i])
DFS(i);
if(cir){printf("-1");return 0;}
int nans=0;
for(int i=1;i<=n;i++){
int res=min(DP(i),RDP(i));
if(res==i) ans[i]='A',nans++;
else ans[i]='E';
}
printf("%d\n%s\n",nans,ans+1);
return 0;
}
|
THE END
Thanks for reading!
> Linked OI Diary-Madia Lemon-Bilibili