Topcoder SRM568 Div1 DisjointSemicircles (二分图染色)

题意: 给定数轴上排列的$2n$个点，每个点需要找到另一个点和它匹配，并且以他们为直径两端，向上或者向下作一个半圆

有一些点已经匹配好了，要求判断是否存在一个合法的方案，满足所有的半圆不相交

思路:

枚举已经确定的匹配半圆的方向(设有$m$对已匹配)，然后$O(n)$判断自由点是否存在合法方案

判断合法方案的核心性质:

定义一个点的方向为其所连接的半圆的方向(上为0，下为1)

则自由点存在合法方案的充要条件是:

整个序列上每种方向的点数为偶数，且所有已匹配的半圆所覆盖的区间下，和半圆同向的点个数为偶数

必要性:

如果某个半圆下同向点个数为奇数，则必然有一个点与其同向并且不得不连到区间外，这显然不合法

充分性:

一种合法的构造方法是:

按照$L$从左到右，遍历每个已匹配的半圆，如果包含同向子半圆优先解决同向的子半圆

剩下的点依然是偶数个，从左到右依次和上一个匹配即可

判断是否存在合法方案

那么问题转化为判断是否存在一种合法的定向方案，使得某一些区间里0/1的个数为偶数

考虑构建二分图染色，令点集$V=\{0,1,\cdots,n,0’,1’,\cdots,n’\}$，则$(u,v)\in E$表示$col(u)\ne col(v)$

其中$i$号节点表示$1-i$中所有未匹配节点方向的异或和，$i’$表示$i$的反点$(i,i’)\in E$

(到这里可以自己想一下怎么连边)

对于已匹配圆$[L,R]$ (注意不要忘了$[1,n]$)

如果它方向为$1$，显然只需要$col(L-1)=col(R)$

如果方向为0，设$[L,R]$未染色个数为$k$，则显然有$col(L-1)=col(R)\oplus (k\mod 2)$，即考虑反向的个数

同时对于已匹配点$i$，显然有$col(i)=col(i-1)$

由此，得到一个$O(n)$点数边数的图

如果在$\text{dfs}$枚举时同步加边和回撤，总复杂度就为$O(2^m\cdot 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
74
75
76
77
78
79
80
81
82
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)

const int N=110;

int n;
int a[N];
int cnt[N];
int L[N],R[N],m,Cross[N][N];
int vec[2][N],c[2];

struct Edge{
	int u,v,nxt;
}e[N*10];
int head[N],ecnt;
void AddEdge(int u,int v) {
	e[++ecnt]=(Edge){u,v,head[u]};
	head[u]=ecnt;
}
void Link(int u,int v){ 
	AddEdge(u,v),AddEdge(v,u); 
}
void Back(){
	head[e[ecnt].u]=e[ecnt].nxt,ecnt--;
	head[e[ecnt].u]=e[ecnt].nxt,ecnt--;
}

int ans,fl;
int vis[N];
void dfs_col(int u,int c){
	vis[u]=c;
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].v;
		if(!vis[v]) dfs_col(v,3-c);
		else if(vis[v]==vis[u]) fl=0;
	}
}

void dfs(int p) {
	if(ans) return;
	if(p>m){
		rep(i,0,n*2+1) vis[i]=0;
		fl=1;
		rep(i,0,n*2+1) if(!vis[i]) dfs_col(i,1);
		ans|=fl;
		return;
	}
	rep(i,0,1){
		int fl=1;
		rep(j,1,c[i]) if(R[vec[i][j]]>L[p] && R[vec[i][j]]<R[p]) fl=0;
		if(!fl) continue;
		vec[i][++c[i]]=p;
		if(i || ~(cnt[R[p]]-cnt[L[p]])&1) Link(L[p]+n+1,R[p]-1);
		else Link(L[p],R[p]-1);
		dfs(p+1);
		c[i]--,Back();
	}
}

class DisjointSemicircles {
public:
	string getPossibility(vector <int> labels) {
		n=labels.size(),m=0;
		rep(i,1,n) a[i]=labels[i-1];
		rep(i,1,n) {
			cnt[i]=cnt[i-1]+(a[i]==-1);
			if(~a[i]) rep(j,i+1,n) if(a[j]==a[i]) L[++m]=i,R[m]=j;
		}
		if(!m) return "POSSIBLE";
		rep(i,0,(n+1)*2) head[i]=ecnt=0;
		rep(i,1,n) if(~a[i]) Link(i+n+1,i-1);
		rep(i,0,n) Link(i,i+n+1);
		Link(n+1,n);
		ans=0,dfs(1);
		return ans?"POSSIBLE":"IMPOSSIBLE";
	}
};