Prince and Princess

Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 1165    Accepted Submission(s): 325

2
4 4
2 1 2
2 1 2
2 2 3
2 3 4
1 2
2 1 2

Case #1:
2 1 2
2 1 2
1 3
1 4
Case #2:
2 1 2

Statistic | Submit | Discuss
|
Note

首先做一次最大匹配，设为cnt，那么对于左边，有n-cnt个王子没有匹配，对于右边，有m-cnt个公主没有匹配，所以我们在左边加上m-cnt个虚拟点，这些点喜欢所有公主，右边加上n-cnt个虚拟点，这些点被所有王子喜欢，这样左右两边都是n+m-cnt个点，在求一次最大匹配，这一定是一个完备匹配，对于每一个王子，用他目前匹配的公主，向所有他喜欢的公主连一条有向边，这表示单方面可以替换，所以再对得到的新图求强连通，处在一个强连通分量的公主可以相互替换

/*************************************************************************
    > File Name: hdu4685.cpp
    > Author: ALex
    > Mail: 405045132@qq.com 
    > Created Time: 2015年01月21日 星期三 15时10分15秒
 ************************************************************************/

#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1100;

int head[N];
int DFN[N];
int low[N];
int block[N];
int match[N];
int match2[N];
bool used[N];
bool instack[N];
bool g[N][N];
stack <int> st;
vector <int> vis;
int n, m, tot, sccnum, ord, num_v, num_u;

struct node
{
	int next;
	int to;
}edge[N * N * 5];

void init ()
{
	vis.clear();
	memset (g, 0, sizeof(g));
	memset (match, -1, sizeof(match));
	memset (match2, -1, sizeof(match2));
	memset (used, 0, sizeof(used));
	memset (instack, 0, sizeof(instack));
	memset (DFN, -1, sizeof(DFN));
	memset (low, 0, sizeof(low));
	memset (head, -1, sizeof(head));
	tot = sccnum = ord = 0;
}

void addedge (int from, int to)
{
	edge[tot].to = to;
	edge[tot].next = head[from];
	head[from] = tot++;
}

bool dfs (int u)
{
	for (int i = 1; i <= num_v; ++i)
	{
		if (!g[u][i])
		{
			continue;
		}
		int v = i;
		if (!used[v])
		{
			used[v] = 1;
			if (match[v] == -1 || dfs (match[v]))
			{
				match[v] = u;
				return 1;
			}
		}
	}
	return 0;
}

int hungry ()
{
	int cnt = 0;
	for (int i = 1; i <= num_u; ++i)
	{
		memset (used, 0, sizeof(used));
		if (dfs(i))
		{
			++cnt;
		}
	}
	return cnt;
}

void tarjan (int u)
{
	DFN[u] = low[u] = ++ord;
	instack[u] = 1;
	st.push(u);
	for (int i = head[u]; ~i; i = edge[i].next)
	{
		int v = edge[i].to;
		if (DFN[v] == -1)
		{
			tarjan (v);
			low[u] = min (low[v], low[u]);
		}
		else if (instack[v])
		{
			low[u] = min (low[u], DFN[v]);
		}
	}
	int v;
	if (low[u] == DFN[u])
	{
		++sccnum;
		do
		{
			v = st.top();
			st.pop();
			instack[v] = 0;
			block[v] = sccnum;
		}while (u != v);
	}
}

void solve ()
{
	num_u = n;
	num_v = m;
	int cnt = hungry();
	num_u = n + m - cnt;
	num_v = num_u;
	for (int i = n + 1; i <= num_u; ++i)
	{
		for (int j = 1; j <= num_v; ++j)
		{
			g[i][j] = 1;
		}
	}
	for (int i = 1; i <= num_u; ++i)
	{
		for (int j = m + 1; j <= num_v; ++j)
		{
			g[i][j] = 1;
		}
	}
//	printf("%d\n", cnt);
	memset (match, -1, sizeof(match));
	cnt = hungry();
//	printf("%d\n", cnt);
	for (int i = 1; i <= num_v; ++i)
	{
		if (match[i] != -1)
		{
			match2[match[i]] = i;
		}
	}
	for (int i = 1; i <= num_u; ++i)
	{
		for (int j = 1; j <= num_v; ++j)
		{
			if (g[i][j] && match2[i] != j)
			{
				addedge (match2[i], j);
			}
		}
	}
	for (int i = 1; i <= num_v; ++i)
	{
		if (DFN[i] == -1)
		{
			tarjan (i);
		}
	}
	for (int i = 1; i <= n; ++i)
	{
		vis.clear();
		for (int j = 1; j <= m; ++j)
		{
			if (g[i][j] && block[j] == block[match2[i]])
			{
				vis.push_back (j);
			}
		}
		int tmp = vis.size();
		printf("%d", tmp);
		for (int j = 0; j < tmp; ++j)
		{
			printf(" %d", vis[j]);
		}
		printf("\n");
	}
}

int main ()
{
	int t;
	int u, v, num;
	int icase = 1;
	scanf("%d", &t);
	while (t--)
	{
		scanf("%d%d", &n, &m);
		init();
		for (int i = 1; i <= n; ++i)
		{
			scanf("%d", &num);
			while (num--)
			{
				scanf("%d", &v);
				g[i][v] = 1;
			}
		}
		printf("Case #%d:\n", icase++);
		solve();
	}
	return 0;
}