crazy_cloud's Blog
0%

2017-2018 Asia Daejeon J, Strongly Matchable

Posted on Edited on In

题目大意

给一幅 \(n\) 个点的无向无权简单图。

判断是否对于任意一种把点涂成 \(\frac n2\) 个黑点和 \(\frac n2\) 个白点的染色方式，都存在黑白点之间的完美匹配。

\(1\leq n\leq 100\) 且为偶数。

题目分析

既然是考察完美匹配的存在性，首先肯定要使用霍尔定理。

如果存在黑点集 \(U(|U|\leq\frac n2)\)，使得其邻集 \(\delta(U)\) 中的白点数量要 \(<|U|\)，那么肯定是不存在完美匹配的。

考虑最坏的情况，就是剩下 \(\frac n2-|U|\) 个黑点全部分配在 \(\delta(U)\) 里面，即白点的数目最少的时候是 \(|\delta(U)|-\left(\frac n2-|U|\right)\)。

移项得到题目要求为一个点集 \(U(|U|\leq\frac n2)\) 使得 \(|\delta(U)|<\frac n2\)。

然后咋做呢？考虑 \(U’\) 为 \(V\backslash U\backslash\delta(U)\)，因为 \(|U|\leq \frac n2\) 而 \(|\delta(U)|<\frac n2\)，所以 \(|U’|\) 一定非空。那么实际上 \(\delta(U)\) 就是 \(U\) 和 \(U’\) 的点割！

同时我们还要说明只要存在点割 \(C\) 满足 \(|C|<\frac n2\) 一定能构造出 \(U\)，这个很显然，因为对于任何点割 \(X-C-Y\) 都一定有 \(|X|\leq\frac n2\) 或者 \(|Y|\leq\frac n2\)。

然后问题解决了，只需要枚举源点和汇点然后跑网络流判定最小点割是否 \(<\frac n2\) 就好了。

时间复杂度 \(O\left(n^2\mathrm{maxflow}(n,n^2)\right)\)。

代码实现

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
#include <algorithm>
#include <iostream>
#include <climits>
#include <cstring>
#include <cstdio>
#include <cctype>
#include <queue>

using namespace std;

inline int read()
{
	int x=0,f=1;
	char ch=getchar();
	while (!isdigit(ch)) f=ch=='-'?-1:f,ch=getchar();
	while (isdigit(ch)) x=x*10+ch-'0',ch=getchar();
	return x*f;
}

const int N=105;
const int M=N*N;

int edge[M][2];
bool fail;
int n,m;

namespace network
{
	const int INF=INT_MAX>>2;
	const int V=N<<1;
	const int E=N+(M<<1)<<1;

	int tov[E],nxt[E],f[E],v[E],r[E];
	int last[V],lab[V];
	int S,T,tot;
	queue<int> q;

	inline void insert(int x,int y,int full,int rev){tov[++tot]=y,nxt[tot]=last[x],f[tot]=full,r[tot]=tot+rev,last[x]=tot;}
	inline void addedge(int x,int y,int full){insert(x,y,full,1),insert(y,x,0,-1);}

	inline bool relabel()
	{
		for (int x=1;x<=n*2;++x) lab[x]=0;
		for (lab[S]=1,q.push(S);!q.empty();q.pop())
			for (int x=q.front(),i=last[x],y;i;i=nxt[i])
				if (!lab[y=tov[i]]&&f[i]-v[i])
					lab[y]=lab[x]+1,q.push(y);
		return lab[T];
	}

	int aug(int x,int flow)
	{
		if (x==T) return flow;
		int ret=0;
		for (int i=last[x],y;i;i=nxt[i])
			if (lab[y=tov[i]]==lab[x]+1&&f[i]-v[i])
			{
				int tmp=aug(y,min(flow,f[i]-v[i]));
				if (tmp)
				{
					ret+=tmp,flow-=tmp;
					v[i]+=tmp,v[r[i]]-=tmp;
					if (!flow) break;
				}else lab[y]=0;
			}
		return ret;
	}

	inline int maxflow()
	{
		int ret=0;
		for (int tmp;relabel();) for (;tmp=aug(S,INF);ret+=tmp);
		return ret;
	}

	inline void build(int s,int t)
	{
		memset(tov,0,sizeof tov),memset(nxt,0,sizeof nxt),memset(f,0,sizeof f),memset(v,0,sizeof v),memset(last,0,sizeof last),tot=0;
		S=s<<1,T=(t<<1)-1;
		for (int x=1;x<=n;++x)
			if (x!=s&&x!=t) addedge((x<<1)-1,x<<1,1);
		for (int i=1,x,y;i<=m;++i)
		{
			x=edge[i][0],y=edge[i][1];
			addedge(x<<1,(y<<1)-1,INF),addedge(y<<1,(x<<1)-1,INF);
		}
	}
};

int main()
{
	freopen("smatch.in","r",stdin),freopen("smatch.out","w",stdout);
	n=read(),m=read();
	for (int i=1;i<=m;++i) edge[i][0]=read(),edge[i][1]=read();
	fail=0;
	for (int s=1;!fail&&s<n;++s)
		for (int t=s+1;!fail&&t<=n;++t)
			network::build(s,t),fail=network::maxflow()<<1<n;
	printf("%d\n",fail?-1:1);
	fclose(stdin),fclose(stdout);
	return 0;
}