Prince and Princess

神题。。。。。。

本蒟蒻又刷到一个难题。不会做

查了题解后发现这是poj1904的变种。我只想说这题太牛逼了。
给出poj1904的题解：
https://www.cnblogs.com/zxndgv/archive/2011/08/06/2129333.html
其实还是增广路的思想。
由此引发到了强连通分量。
这让我想到了以前做过的一道题，记得是判断最小割中割边的唯一性。好像也是用到了强连通分量。
真的是非常巧妙，要对增广路有十分清晰的认识。同时，还应该充分利用完美匹配的条件。
真的是太强了。
至于这道题，我们因为刚开始不是完美匹配所以需要构造完美匹配：
见题解：https://blog.csdn.net/birdmanqin/article/details/99675178

大佬在这里说：新建虚拟节点使得其变为完美匹配，然后就可以利用完美匹配的性质了。
而这个新建节点，虚拟王子则是喜欢所有真实公主，虚拟公主则是要被所有真实王子喜欢

为什么要这样建立节点呢？？
在poj1904中，大佬的分析中说了至关重要的一句话：
我们从xj开始找增广路，如果能找到一条增广路，那么根据完美匹配的性质这条增广路的末端一定是yi
因此我们只需要连接yi->xi就可以利用强连通分量找他了。

那么，来看看我们这里的情况：
假设是这样的一个图：

红色为王子，黑色为公主。
红2为虚构的王子。
我们发现在这种情况下求解出来的并不是正确答案。
因为在虚构节点这种连接方式之下，我们无法找到从2开始的一条增广路最终指向公主1
所以我们应该让虚拟王子只想所有真实公主，才能保证在通过虚拟接待你找增广路时一定能成功。
因为寻你节点毕竟是虚拟的啊，我们不用为其安排配对。
我说的很不好，实在是抱歉。希望能该你一点启发。
然后最后还有一个坑点：就是我们要判断是否有这条边使得王子瑜公主连接，具体见代码

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<stack>
#include<vector>
using namespace std;
const int inf = 2e9;
const int max_n = 2100;
const int max_m = max_n * max_n;
struct edge{
    int to, next;
}E[max_m << 1];
int head[max_n];
int cnt = 1;
void add(int from, int to) {
    E[cnt].to = to;E[cnt].next = head[from];
    head[from] = cnt++;
}
int leftTo[max_n], rightTo[max_n];
int distleft[max_n], distright[max_n];
int dist;
bool seacherpath(int left_tot, int right_tot) {
    fill(distleft, distleft + max_n, -1);
    fill(distright, distright + max_n, -1);
    queue<int> que;dist = inf;
    for (int i = 1;i <= left_tot;++i)
        if (leftTo[i] == -1)
            que.push(i);
    while (!que.empty()) {
        int u = que.front();que.pop();
        if (distleft[u] > dist)break;
        for (int i = head[u];i;i = E[i].next) {
            int v = E[i].to;
            if (distright[v] != -1)continue;
            distright[v] = distleft[u] + 1;
            if (rightTo[v] == -1)dist = distright[v];
            else {
                distleft[rightTo[v]] = distright[v] + 1;
                que.push(rightTo[v]);
            }
        }
    }return dist != inf;
}
bool matchpath(int u) {
    for (int i = head[u];i;i = E[i].next) {
        int v = E[i].to;
        if (distright[v] != distleft[u] + 1)continue;
        if (distright[v] == dist && rightTo[v] != -1)continue;
        distright[v] = -1;
        if (rightTo[v] == -1 || matchpath(rightTo[v])) {
            leftTo[u] = v;
            rightTo[v] = u;
            return true;
        }
    }return false;
}int HK(int left_tot, int right_tot) {
    fill(leftTo, leftTo + max_n, -1);
    fill(rightTo, rightTo + max_n, -1);
    int ans = 0;
    while (seacherpath(left_tot, right_tot)) {
        for (int i = 1;i <= left_tot;++i)
            if (leftTo[i] == -1 && matchpath(i))
                ++ans;
    }return ans;
}

int dfn[max_n], low[max_n];
int tot0 = 0;
stack<int> st;
int color[max_n];
int colour = 0;
void tarjan(int u) {
    dfn[u] = low[u] = ++tot0;
    st.push(u);
    for (int i = head[u];i;i = E[i].next) {
        int v = E[i].to;
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        }
        else if (color[v] == 0)low[u] = min(low[u], dfn[v]);
    }if (low[u] != dfn[u])return;
    colour++;
    while (st.top() != u) {
        color[st.top()] = colour;
        st.pop();
    }color[st.top()] = colour;st.pop();
}

vector<int> nums[max_n];
bool mp[550][550];
int main() {
    int T;scanf("%d", &T);int n, m;
    for (int tcase = 1;tcase <= T;++tcase) {
        fill(head, head + max_n, 0);cnt = 1;
        fill(dfn, dfn + max_n, 0);
        fill(color, color + max_n, 0);
        for (int i = 0;i < 550;++i)for (int j = 0;j < 550;++j)mp[i][j] = false;
        colour = tot0 = 0;
        for (int i = 0;i < max_n;++i)nums[i].clear();
        scanf("%d %d", &n, &m);
        for (int u = 1, len;u <= n;++u) {
            scanf("%d", &len);
            for (int i = 1, v;i <= len;++i) {
                scanf("%d", &v);
                add(u, v + n);
                mp[u][v] = true;
            }
        }HK(n, n + m);
        int tot = n + m;
        for (int u = 1;u <= n;++u) {
            if (leftTo[u] == -1) {
                leftTo[u] = ++tot;
                rightTo[tot] = u;
                add(leftTo[u], u);
                for (int i = 1;i <= n;++i)
                    add(i, tot);
            }else add(leftTo[u], u);
        }for (int v = n + 1;v <= n + m;++v) {
            if (rightTo[v] == -1) {
                rightTo[v] = ++tot;
                leftTo[tot] = v;
                add(v, tot);
                for (int i = n + 1;i <= n + m;++i)
                    add(tot, i);
            }
        }for (int i = 1;i <= tot;++i)
            if (!dfn[i])
                tarjan(i);
        printf("Case #%d:\n", tcase);
        for (int i = 1;i <= n;++i) {
            for (int j = n + 1;j <= n + m;++j)
                if (mp[i][j - n] && color[i] == color[j])
                    nums[i].push_back(j - n);
            printf("%d", nums[i].size());
            for (int j = 0;j < nums[i].size();++j)
                printf(" %d", nums[i][j]);
            printf("\n");
        }
    }
}