题意略。
思路:
本题和POJ1904颇为相似,只是那个最大匹配没有现成的,要我们自己求出来。并且要给每一个单身的王子/公主现找一个虚拟的对象。
这也是合乎情理的,王子每一次换一个公主时,可能会导致某一个王子失去他的原配,然而同样也会有另一个单身王子找到公主。
这里注意,每一个虚拟王子要喜欢所有公主,每一个虚拟公主要被所有王子喜欢。
详见代码:
#include<bits/stdc++.h>
using namespace std;
const int maxn = ;int linked[maxn],component[maxn],V,uN,n,m;
bool used[maxn],visit[maxn];
vector<int> store[maxn];
vector<int> G[maxn];
vector<int> rG[maxn];
vector<int> graph[maxn];
vector<int> vs;void add_edge(int from,int to){
G[from].push_back(to);
rG[to].push_back(from);
}
void dfs(int v){
used[v] = true;
for(int i = ;i < G[v].size();++i){
int to = G[v][i];
if(!used[to]) dfs(to);
}
vs.push_back(v);
}
void rdfs(int v,int k){
used[v] = true;
component[v] = k;
for(int i = ;i < rG[v].size();++i){
int to = rG[v][i];
if(!used[to]) rdfs(to,k);
}
}
int scc(){
memset(used,false,sizeof(used));
vs.clear();
for(int v = ;v <= V;++v){
if(!used[v]) dfs(v);
}
memset(used,false,sizeof(used));
int k = ;
for(int i = vs.size() - ;i >= ;--i){
if(!used[vs[i]]) rdfs(vs[i],k++);
}
return k;
}
bool dfs1(int u){
for(int i = ;i < graph[u].size();++i){
int v = graph[u][i];
if(used[v]) continue;
used[v] = true;
if(linked[v] == - || dfs1(linked[v])){
linked[v] = u;
return true;
}
}
return false;
}
int hungary(){
int ret = ;
memset(linked,-,sizeof(linked));
for(int u = ;u <= uN;++u){
memset(used,false,sizeof(used));
if(dfs1(u)) ++ret;
}
return ret;
}
void init(){
memset(component,,sizeof(component));
memset(visit,false,sizeof(visit));
for(int i = ;i < maxn;++i){
G[i].clear();
rG[i].clear();
store[i].clear();
graph[i].clear();
}
uN = n;
}int main(){
int T,cas = ;
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&m);
init();
for(int i = ;i <= n;++i){
int ki;
scanf("%d",&ki);
int t;
for(int j = ;j < ki;++j){
scanf("%d",&t);
graph[i].push_back(t);
add_edge(i,t + n);
}
}
int temp = hungary();
int tn = n - temp,tm = m - temp;
for(int i = ;i <= m;++i){
int from = i + n,to = linked[i];
if(to == -) continue;
add_edge(from,to);
visit[to] = true;
}
for(int i = n + m + ;i <= n + m + tm;++i){
bool signal = true;
for(int j = n + ;j <= n + m;++j){
add_edge(i,j);
if(signal && linked[j - n] == -){
signal = false;
add_edge(j,i);
linked[j - n] = i;
}
}
}
for(int i = n + m + tm + ;i <= n + m + tm + tn;++i){
bool signal = true;
for(int j = ;j <= n;++j){
add_edge(j,i);
if(visit[j] == false && signal){
signal = false;
visit[j] = true;
add_edge(i,j);
}
}
}
V = n + m + tm + tn;
int numb = scc();
for(int i = ;i <= n;++i){
for(int j = ;j < graph[i].size();++j){
int to = graph[i][j] + n;
if(to > n + m) continue;
int belong1 = component[i],
belong2 = component[to];
if(belong1 == belong2){
store[i].push_back(to - n);
}
}
sort(store[i].begin(),store[i].end());
}
printf("Case #%d:\n",cas++);
for(int i = ;i <= n;++i){
printf("%d",store[i].size());
for(int j = ;j < store[i].size();++j){
printf(" %d",store[i][j]);
}
printf("\n");
}
}
return ;
}