OI - Adopt or not (HDU) | Lucky_Glass's Blog

以心为名，名为爱惜

0%

OI - Adopt or not (HDU)

发表于 分类于 Valine：

为什么这道题网上的博客这么少啊 QAQ
（算了 我自己写一篇……）

Part1. 题意

有两个政党，称为 A,B。在一次大会中，A 提出了 $a$ 个提议（A 提出的提议编号为 1~a），B 提出了 $b$ 个提议（编号为 a+1~a+b）。

大会有 $n$ 名议员，第 $i$ 名议员赞成第 $p_i$ 个提议，反对 $Q_i=\{q_{i,1},q_{i,2}\cdots q_{i,m_i}\}$ 这 $m_i$ 个提议。由于议员都偏向于某一个党派，所以他赞成的提议与反对的提议一定是不同的党派提出的。

作为大会的主席，你要决定采取一些提议。如果某一个议员赞成的提议被采取了，且所有他反对的提议都没有被采取，他就会非常高兴。

你希望知道最多能同时使多少个议员高兴。并且求出，在使高兴的议员数量最多的情况下，哪些提议是必须采取的（即求出哪些提议在每一个“高兴的议员数量最多”的方案中都被采取）。

数据规模：$1\le a,b\le100,1\le n\le200$。

Part2. 解析

题面非常显然地分成了两个点集，而且每个议员相当于一些边，连接两个点集的点。然后就想到了二分图。

Part2/1. 建图

由于两个议员可能赞成同一个提议，而且每个提议不一定都有人赞成，可以发现将每个提议建点并不如将每个议员建点。

那么考虑连边。题目中所述的，议员的赞成的提议和不赞成的提议其实形成了“两个点不能同时产生贡献”的关系 —— 对于议员 $i$ 和 $j$，如果 $p_i\in Q_j$ 且 $p_j\in Q_i$，那么显然 $i$ 和 $j$ 就无法同时产生贡献。

在图论中，这样不能同时产生贡献的关系，比如独立集。

于是考虑这样建图，将 $n$ 个议员按他们支持的提议 $p_i$ 是属于哪个党派，分成二分图的两个部。对于不同部的两个议员 $i$ 和 $j$，如果 $p_i\in Q_j$ 且 $p_j\in Q_i$，则连接边 $(i,j)$。

Part2/2. 最大独立集

因为连了边表示两个点不能同时产生贡献，那么最多能让多少个点产生贡献其实就是最大独立集。

如果你知道二分图的 最大独立集、最小点覆盖、最大匹配 这三个值的关系的话，求最大独立集就很 easy 了。即 n-最大匹配。

> Tip
结论就是 最大匹配=最小点覆盖=n-最大独立集；就不给出证明了

这道题……不知道匈牙利算法跑不跑得过……毕竟它太慢了。跑最大匹配比较快的方法，首先是时间复杂度玄学的网络流 Dinic（因为二分图是一个特殊的分层图嘛），还有长得很像 Dinic 的 HK 算法（其实我是现学的 HK 算法 awa）。

和 Dinic 的思路很像 —— Dinic 每次找最短的增广路，HK 也一样，每次增广最短的增广路。

甚至也用 BFS() 找增广路，只是略微有一点不同，感受一下：

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
bool BFS(){
	for(int i=1;i<=n;i++)
		depx[i]=depy[i]=0;
	queue< int > que;
	for(int i=1;i<=a;i++)
		for(int j=1;j<=nidx[i];j++){
			if(mat[idx[i][j]]) continue;
			que.push(idx[i][j]);
			depx[idx[i][j]]=1;
		}
	bool resu=false;
	while(!que.empty()){
		int u=que.front();que.pop();
		for(NODE *it=G[u];it;it=it->nxt){
			int v=it->to;
			if(!depy[v]){
				depy[v]=depx[u]+1;
				if(mat[v]){
					depx[mat[v]]=depy[v]+1;
					que.push(mat[v]);
				}
				else resu=true;
			}
		}
	}
	return resu;
}

一开始向队列里面插入所有 还未匹配 的 X 部的点，然后从 X 部的一个点 $u$ 向外找到一个未访问过的 Y 部的点 $v$。如果这个点 $v$ 没有匹配过，就说明找到增广路，打上标记（就不插入队列了）；如果匹配过，就把匹配到的 X 部的点更新，并插入队列。

每 BFS() 一次就从 X 部的每个节点做一次增广，直到 BFS() 找不到增广路为止。

1
2
3
4
5
6
7
while(BFS())
	for(int i=1;i<=a;i++)
		for(int j=1;j<=nidx[i];j++)
			if(!mat[idx[i][j]]){
				ntmp++;
				resu+=Aug(idx[i][j],true);
			}

还是很像 Dinic @.@。复杂度跟网络流跑二分图的理论复杂度一样，不过更加稳定，是 $O(\sqrt nm)$

Part2/3. 最大独立集的关键点

其实题目描述的就是关键点的定义 —— 如果一个点出现在所有最大独立集中（最大独立集可能有多个），那么该点称为最大独立集的关键点。

我们知道“最大独立集=点数-最大匹配”，那么可以利用这一个性质来求某一个点是否是关键点：

  1. 如果点 $u$ 没有匹配，则它一定出现在最大独立集中，即是关键点；
  2. 否则，暂时删去与 $u$ 匹配的点 $mat_u$，重新找一条从 $u$ 开始的增广路。如果找到了，此时的最大匹配不变，但是点数减少$1$（因为删去了$mat_u$），所以最大独立集会减小，说明 $mat_u$ 是关键点（注意不是 $u$）。

这样的话就可以过了。（只是处理输入数据比较麻烦）

Part3. 源代码

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
136
137
138
139
140
141
142
143
144
145
146
147
148
/*Lucky_Glass*/
#pragma GCC optimize(2)
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=200;

int a,b,n,del;
int nidx[N+3],idx[N+3][N+3];
int depx[N+3],depy[N+3],mat[N+3];
int ntmp,tmp[N+3],col[N+3];
bool ans[N+3];

struct MEMBER{
	int lik;
	int ndlik,dlik[N+3];
	int& operator [](int id){return dlik[id];}
}mem[N+3];

struct NODE{
	int to;NODE *nxt;
	NODE(){}
	NODE(int _t,NODE *_n):to(_t),nxt(_n){}
};
struct GRAPH{
	NODE pol[N*N*2+3],*head[N+3],*ncnt;
	void Init(){
		ncnt=pol;
		for(int i=1;i<=n;i++) head[i]=NULL;
	}
	void AddEdge(int u,int v){
		NODE *p=++ncnt,*q=++ncnt;
		*p=NODE(v,head[u]);head[u]=p;
		*q=NODE(u,head[v]);head[v]=q;
	}
	NODE* operator [](int id){return head[id];}
}G;

bool BFS(){
	for(int i=1;i<=n;i++)
		depx[i]=depy[i]=0;
	queue< int > que;
	for(int i=1;i<=a;i++)
		for(int j=1;j<=nidx[i];j++){
			if(mat[idx[i][j]]) continue;
			que.push(idx[i][j]);
			depx[idx[i][j]]=1;
		}
	bool resu=false;
	while(!que.empty()){
		int u=que.front();que.pop();
		for(NODE *it=G[u];it;it=it->nxt){
			int v=it->to;
			if(!depy[v]){
				depy[v]=depx[u]+1;
				if(mat[v]){
					depx[mat[v]]=depy[v]+1;
					que.push(mat[v]);
				}
				else resu=true;
			}
		}
	}
	return resu;
}
bool Aug(int u,bool hk){
	if(tmp[u]==ntmp) return false;
	tmp[u]=ntmp;
	for(NODE *it=G[u];it;it=it->nxt){
		int v=it->to;
		if(hk && depy[v]!=depx[u]+1) continue;
		if(v==del) continue;
		if(!mat[v] || Aug(mat[v],hk)){
			mat[mat[v]=u]=v;
			return true;
		}
	}
	return false;
}
bool Check(int u){
	if(tmp[u]==ntmp) return false;
	tmp[u]=ntmp;
	for(NODE *it=G[u];it;it=it->nxt){
		int v=it->to;
		if(v==del) continue;
		if(!mat[v] || Check(mat[v]))
			return true;
	}
	return false;
}
int Match(){
	for(int i=1;i<=n;i++) mat[i]=tmp[i]=0;
	int resu=0;
	while(BFS())
		for(int i=1;i<=a;i++)
			for(int j=1;j<=nidx[i];j++)
				if(!mat[idx[i][j]]){
					ntmp++;
					resu+=Aug(idx[i][j],true);
				}
	return resu;
}
int main(){
	int cas;scanf("%d",&cas);
	while(cas--){
		scanf("%d%d%d",&a,&b,&n);
		
		ntmp=del=0;
		G.Init();
		for(int i=1;i<=a+b;i++)
			nidx[i]=ans[i]=col[i]=0;
		for(int i=1;i<=n;i++) mem[i].ndlik=0;
		
		for(int i=1;i<=n;i++){
			scanf("%d%d",&mem[i].lik,&mem[i].ndlik);
			for(int j=1;j<=mem[i].ndlik;j++)
				scanf("%d",&mem[i][j]);
			idx[mem[i].lik][++nidx[mem[i].lik]]=i;
			col[i]=mem[i].lik;
		}
		for(int i=1;i<=n;i++)
			for(int j=1;j<=mem[i].ndlik;j++)
				for(int k=1;k<=nidx[mem[i][j]];k++)
					G.AddEdge(i,idx[mem[i][j]][k]);
		int mx=Match();
		for(int i=1;i<=n;i++)
			if(mat[i]){
				del=mat[i];
				ntmp++;
				if(Check(i))
					ans[col[mat[i]]]=true;
			}
			else ans[col[i]]=true;
		int nans=0;
		for(int i=1;i<=a+b;i++)
			if(ans[i])
				nans++;
		printf("%d\n%d",n-mx,nans);
		for(int i=1;i<=a+b;i++)
			if(ans[i])
				printf(" %d",i);
		printf("\n");
	}
	return 0;
}

The End

Thanks for reading!

唉……