神题。。。。。。
本蒟蒻又刷到一个难题。不会做
查了题解后发现这是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"); } } }