Reincarnation

正因为梦易碎，才格外美好。

适定性问题

发表于 更新于 分类于 ，
本文字数： 12k 阅读时长 ≈ 11 分钟

“正因为如此，并非所有人的梦想，最终都能实现。”

适定性问题

称作 ，是适定性（）问题的简称。当前学术界的理论是，当 时，适定性问题为 完全问题，所以一般而言（一般都不会考），涉及到的只有 问题。

次适定性问题的描述在于，对于一个长度为 的 序列，有 个条件，每一个条件会适定 个元素，由 组成，对 中的 个进行限制。

例如：

使得 ，其中 ，任意的 前面都可以存在 。

再给一个更详细的例子：

设定 ，有限制 ，则有解 。

二次适定性问题

即每一个条件最终只有两个元素互相限制，这个问题可以在线性时间内（大概是 内）解决。也存在一种 的做法，用于求解最小字典序之类的问题，但是效率较为低下。

求解

离散数学中有一章名为《数与逻辑》提到一个结论：

其中 表示推导，其余符号与上述相同。

我们可以从这个地方开始扩展：

在 界，大多数人都会把推导符号幻视成一个东西：图。那我们就从这个地方入手。

实现

我们考虑从 向 连接一条有向边，并从 向 连接一条有向边。这样会形成一个图，那么对于这个图中的任意一条路径，就是一个子解。

这张图有 个结点，对于每一个 有两个结点，分别表示 和 成立的情况，那么显然地， 和 不可能同时成立。所以当一条完整路径既包括 又包括 时，则证明当前问题是无解的。

但显然，对于一张图而非一棵树，完整路径是可以中途”转弯“的，所以，实际上的无解情况其实是——当 和 被包含在同一个环里的时候。

那就要找到图中的所有环了，找有向图环，当然就需要用到 算法（其他的也行），保证复杂度线性。

对于求解，我们依然可以使用强连通分量的性质：

  • 进行拓扑排序（强连通分量编号即为反向拓扑序）；
  • 对于每一个缩点，选出拓扑大（强连通分量小）的。

这样的话， 问题就结束了。

参考代码
 
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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
// ----- Eternally question-----
// Problem: P4782 【模板】2-SAT 问题
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4782
// Memory Limit: 512 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2022-12-12 17:15:58
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ std::cout<<x; }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=2e6+10;
int N,M;
struct G
{
	int next,to;
}Edge[MAXN<<1];
int Head[MAXN],Total;
inline void addEdge(int u,int v)
{
	// Edge[++Total]=(G){Head[u],v};Head[u]=Total;
	Edge[++Total]=(G){Head[v],u};Head[v]=Total;
}
int Dfn[MAXN],Low[MAXN],Stk[MAXN],Top,Cnt;
bool Ins[MAXN];
int Sizc[MAXN],Scc[MAXN],Sc;
void Tarjan(int x)
{
	Dfn[x]=Low[x]=++Cnt,Stk[++Top]=x,Ins[x]=1;
	for(int e=Head[x],v;e;e=Edge[e].next)
	{
		if(!Dfn[(v=Edge[e].to)])
		{
			Tarjan(v);
			checkMin(Low[x],Low[v]);
		}
		else if(Ins[v]) checkMin(Low[x],Dfn[v]);
	}
	if(Dfn[x]==Low[x])
	{
		++Sc;
		while(Stk[Top]!=x)
		{
			Scc[Stk[Top]]=Sc,++Sizc[Sc];
			Ins[Stk[Top]]=0,--Top;
		}
		Scc[x]=Sc,++Sizc[Sc],Ins[x]=0;
		--Top;
	}
}
inline bool check()
{
	for(int i=1;i<=N;++i) if(Scc[i]==Scc[i+N]) return 0;
	return 1;
}
int main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N,M);
	for(int u,a,v,b;M--;)
	{
		read(u,a,v,b);
		addEdge(u+a*N,v+(!b)*N),addEdge(v+b*N,u+(!a)*N);
	}
	for(int x=1;x<=(N<<1);++x) if(!Dfn[x]) Tarjan(x);
	if(check())
	{
		puts("POSSIBLE");
		for(int i=1;i<=N;++i) write(Scc[i]>=Scc[i+N],' ');
	}
	else puts("IMPOSSIBLE");
	return 0;
}
/*

*/

建图不能乱建，考虑每一条边的意义，当 不成立时 必须成立。

例题

P4171 [JSOI2010] 满汉全席

题目比较复杂，大概读一下，容易发现，菜品只有 m 和 h 两种类型，其余的就是对编号 的限制，那我们把两种类型的菜品视为一个布尔变量的 ，拿着就是对 个布尔变量赋值的适定性问题，用 求解即可。

需要注意的地方：

  • 多测清空（ 吃大亏），不要想着占时空上的小便宜，想清楚那些必须清空，那些不必要。
  • 二倍空间。
  • 读入的时候考虑将字符串转换为数字的操作，有 ，那就不止一位。
  • 对于局部变量，要记得赋初值。

那这道题就做完了。

AC Code
 
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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
// ----- Eternally question-----
// Problem: P4171 [JSOI2010] 满汉全席
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4171
// Memory Limit: 128 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2022-12-15 19:29:26
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ std::cout<<x; }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=2e2+10,MAXM=1e5+10;
int N,M;
struct G
{
	int next,to;
}Edge[MAXM<<1];
int Head[MAXN],Total=1;
inline void addEdge(int u,int v)
{
	Edge[++Total]=(G){Head[u],v};Head[u]=Total;
	// Edge[++Total]=(G){Head[v],u};Head[v]=Total;
}
int Dfn[MAXN],Low[MAXN],Stk[MAXN],Cnt,Top;
bool Ins[MAXN];
int Scc[MAXN],Sizc[MAXN],Sc;
void Tarjan(int x)
{
	Dfn[x]=Low[x]=++Cnt,Ins[x]=1,Stk[++Top]=x;
	for(int e=Head[x],v;e;e=Edge[e].next)
	{
		if(!Dfn[(v=Edge[e].to)])
		{
			Tarjan(v);
			checkMin(Low[x],Low[v]);
		}
		else if(Ins[v]) checkMin(Low[x],Dfn[v]);
	}
	if(Dfn[x]==Low[x])
	{
		++Sizc[++Sc];
		while(Stk[Top]!=x)
		{
			Scc[Stk[Top]]=Sc,++Sizc[Sc];
			Ins[Stk[Top]]=0,--Top;
		}
		Ins[x]=0,Scc[x]=Sc,--Top;
	}
}
int Test;
inline void init()
{
	Cnt=Sc=0;
	std::memset(Dfn,0,sizeof(Dfn));
	std::memset(Scc,0,sizeof(Scc));
	std::memset(Sizc,0,sizeof(Sizc));
	std::memset(Head,0,sizeof(Head)),Total=1;
}
char as[10],bs[10];
struct Task
{
	int u,i,v,j;
	inline void trans(char *a,char *b)
	{
		i=(a[0]=='h'),j=(b[0]=='h');u=v=0;
		int lena=strlen(a),lenb=strlen(b);
		for(int k=1;k<lena;++k) u=(u<<3)+(u<<1)+(a[k]^48);
		for(int k=1;k<lenb;++k) v=(v<<3)+(v<<1)+(b[k]^48);
	}
	inline void chk(){ write(u,' ',i,' ',v,' ',j,'\n'); }
};
int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	read(Test);
	while(Test--)
	{
		read(N,M);
		init();
		for(int i=1;i<=M;++i)
		{
			scanf("%s%s",as,bs);
			Task tmp;tmp.trans(as,bs);// tmp.chk();
			addEdge(tmp.u+(!tmp.i)*N,tmp.v+tmp.j*N),
			addEdge(tmp.v+(!tmp.j)*N,tmp.u+tmp.i*N);
		}
		for(int x=1;x<=(N<<1);++x) if(!Dfn[x]) Tarjan(x);
		bool scd=0;
		for(int x=1;x<=N;++x) if(Scc[x]==Scc[x+N])
		{
			scd=1;puts("BAD");
			break;
		}
		if(!scd) puts("GOOD");
	}
	return 0;
}
/*

*/

P5782 [POI2001] 和平委员会

略读题意，稍微总结一下：

一共有 个布尔变量，有 个限制条件，保证二元组 有 ，且 ，求这 个布尔变量的值。

可以发现，这里的所有适定都是 ，而 只能求 的情况，我们考虑怎么转换。

容易发现，每个二元组 必有一个 ，也必有一个 ，那我们把这个组的限制的另外一个称为其配对，记作 ，那对于 限制而言，我们可以转换为 ，即如果选了 ，则 必须选，因为必须要满足 ，而因为 的选择导致 不能被选，所以只能选 。

但事实上，这样的构造并不能满足 的要求，那我们可以用这个来判定构造合法以及得到答案。

AC Code
 
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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
// ----- Eternally question-----
// Problem: P5782 [POI2001] 和平委员会
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P5782
// Memory Limit: 128 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2022-12-16 09:19:32
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ std::cout<<x; }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=4e4+10,MAXM=1e5+10;
int N,M;
struct G
{
	int next,to;
}Edge[MAXN<<1];
int Head[MAXN],Total=1;
inline void addEdge(int u,int v)
{
	Edge[++Total]=(G){Head[u],v};Head[u]=Total;
	// Edge[++Total]=(G){Head[v],u};Head[v]=Total;
}
int Dfn[MAXN],Low[MAXN],Stk[MAXN],Top,Cnt;
bool Ins[MAXN];
int Scc[MAXN],Sizc[MAXN],Sc;
void Tarjan(int x)
{
	Dfn[x]=Low[x]=++Cnt,Stk[++Top]=x,Ins[x]=1;
	for(int e=Head[x],v;e;e=Edge[e].next)
	{
		if(!Dfn[(v=Edge[e].to)])
		{
			Tarjan(v);
			checkMin(Low[x],Low[v]);
		}
		else if(Ins[v]) checkMin(Low[x],Dfn[v]);
	}
	if(Dfn[x]==Low[x])
	{
		++Sc;
		while(Stk[Top]!=x)
		{
			Scc[Stk[Top]]=Sc,++Sizc[Sc];
			Ins[Stk[Top]]=0,--Top;
		}
		Scc[x]=Sc,++Sizc[Sc],--Top,Ins[x]=0;
	}
}
inline int oth(int x){ return x&1?x+1:x-1; }
int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	read(N,M);
	// for(int i=1;i<=(N<<1);++i) write(oth(i),' ');
	// puts("");
	for(int u,v;M--;)
	{
		read(u,v);
		addEdge(u,oth(v)),addEdge(v,oth(u));
	}
	for(int i=1;i<=(N<<1);++i) if(!Dfn[i]) Tarjan(i);
	bool scd=0;
	for(int i=1;i<=(N<<1);i+=2) if(Scc[i]==Scc[i+1]){ scd=1;break; }
	if(scd) puts("NIE");
	else for(int i=1;i<=(N<<1);i+=2)
		if(Scc[i]<Scc[i+1]) write(i,'\n');
		else write(i+1,'\n');
	return 0;
}
/*

*/
相关文章