思路来源
https://blog.csdn.net/sdj222555/article/details/9990131
预备题目
poj1904 King's Quest
n个(n<=2000)王子,n个公主,
已知第i个王子喜欢ki个公主,以下给出k个数代表各个公主编号
最后给出一种完美匹配,代表第j个公主最终选择了哪个王子
要求求出每个王子的可能喜欢的公主集合,使得王子选这个集合里的任意一个公主
都存在方式能达到完美匹配,依次输出第i个王子的公主集合编号,集合内按增序输出
预备题目题解
王子向自己喜欢的公主连边,在完美匹配中公主选择了哪个王子就向哪个王子连边,
不妨把一对夫妻看作一个点缩点,那么,夫妻A和B能换妻当且仅当A的夫指向B的妻,且B的夫指向A的妻
也就是,在新的缩点后的图里,A和B还位于同一个强连通分量里,
由于强连通分量具有类似的传递性,
即A和B位于一个强连通分量里,B和C位于一个强连通分量里,那么ABC一定在一个强连通分量里
只需要求一次强连通分量,去判断和王子在相同的强连通分量里,有哪几个公主,输出即可
预备题目代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;
const int N=2e3+5;
const int M=2e5+1e4;//2e5+2e3
int head[N*2],cnt;
int low[N*2],dfn[N*2],stack[N*2],par[N*2],num,now,top,tot;
bool In[N*2];
int n,k,v,len;
struct edge{int to,next;}e[M];
vector<int>ans;
int Scan() //输入外挂
{
int res=0,ch,flag=0;
if((ch=getchar())=='-')
flag=1;
else if(ch>='0'&&ch<='9')
res=ch-'0';
while((ch=getchar())>='0'&&ch<='9')
res=res*10+ch-'0';
return flag?-res:res;
}
void Out(int a) //输出外挂
{
if(a>9)
Out(a/10);
putchar(a%10+'0');
}
void init()
{
memset(head,0,sizeof head);
memset(In,0,sizeof In);
memset(low,0,sizeof low);
memset(dfn,0,sizeof dfn);
memset(par,0,sizeof par);
cnt=num=top=tot=0;
}
void add(int u,int v)
{
e[++cnt].to=v;
e[cnt].next=head[u];
head[u]=cnt;
}
void dfs(int u)
{
low[u]=dfn[u]=++num;
In[u]=1;
stack[++top]=u;
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].to;
if(!dfn[v])
{
dfs(v);
low[u]=min(low[u],low[v]);
}
else if(In[v])
{
low[u]=min(low[u],dfn[v]);
}
}
if(low[u]==dfn[u])//环的第一个点
{
tot++;
do
{
now=stack[top--];
par[now]=tot;
In[now]=0;
}while(now!=u);
}
}
int main()
{
while(~scanf("%d",&n))
{
init();
for(int i=1;i<=n;++i)
{
k=Scan();
for(int j=1;j<=k;++j)
{
v=Scan();
add(i,v+n);
}
}
for(int i=1;i<=n;++i)
{
v=Scan();
add(v+n,i);
}
for(int i=1;i<=n;++i)
if(!dfn[i])dfs(i);
for(int u=1;u<=n;++u)
{
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].to;
if(par[u]==par[v])
ans.push_back(v-n);
}
sort(ans.begin(),ans.end());
len=ans.size();
Out(len);
for(int i=0;i<len;i++)
putchar(' '),Out(ans[i]);
ans.clear();
puts("");
}
}
return 0;
}
题目
n(n<=500)个王子,m(m<=500)个公主,n、m未必相等
已知第i个王子喜欢ki个公主,以下给出k个数代表各个公主编号,并不给出最大匹配
要求求出每个王子的可能喜欢的公主集合,使得王子选这个集合里的任意一个公主
都存在方式能达到完美匹配,依次输出第i个王子的公主集合编号,集合内按增序输出
题解
考虑类似poj1904的做法,先求出最大匹配,hungary中dfs的时候cx[]cy[]记录一下两边具体连了谁
cx[i]记录第i个王子选择了哪个公主,cy[j]记录了第j个公主选择了哪个王子
求得一种匹配方案,然后在这种方案里把cx[i]向i连边
考虑没有被匹配的王子cx[k],对每个cx[k]都建一个虚拟公主,使之被cx[k]匹配,且被所有王子喜欢
同理,考虑所有没被匹配的公主cy[l],对每个cy[l]都建一个虚拟王子,使之被cy[l]匹配,且喜欢所有公主
这样如果最大匹配个数为x,没被匹配上的王子为n-x,没被匹配上的公主为m-x
虚拟王子就为m-x个,虚拟公主就为n-x个,总的王子和公主个数各为n+m-x个,
两边王子公主相等之后,再求一遍SCC,将实际存在的公主编号存入王子集合即可
感性理解一下,之所以可行,是王子1匹配了公主A,王子2匹配了虚拟公主B,
1、2、A、B位于同一强连通分量内,就相当于可等价为,王子1匹配了虚拟公主B,王子2匹配了A,二者可换
代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;
const int N=1005;
const int M=N*N;//N*N+N
int head[N*2],cnt;
int cx[N*2],cy[N*2];
int low[N*2],dfn[N*2],stack[N*2],par[N*2],num,now,top,tot;
bool In[N*2],vis[N*2];
int t,n,m,k,v,len,mx,all;
struct edge{int to,next;}e[M];
vector<int>ans;
void init()
{
memset(head,0,sizeof head);
memset(In,0,sizeof In);
memset(low,0,sizeof low);
memset(dfn,0,sizeof dfn);
memset(par,0,sizeof par);
cnt=num=top=tot=0;
}
void add(int u,int v)
{
e[++cnt].to=v;
e[cnt].next=head[u];
head[u]=cnt;
}
void tarjan(int u)
{
low[u]=dfn[u]=++num;
In[u]=1;
stack[++top]=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(In[v])
{
low[u]=min(low[u],dfn[v]);
}
}
if(low[u]==dfn[u])//环的第一个点
{
tot++;
do
{
now=stack[top--];
par[now]=tot;
In[now]=0;
}while(now!=u);
}
}
bool dfs(int u)
{
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].to;
if(!vis[v])
{
vis[v]=1;
if(cy[v]==-1||dfs(cy[v]))
{
cx[u]=v;
cy[v]=u;
return 1;
}
}
}
return 0;
}
int hungary()
{
int res=0;
memset(vis,0,sizeof vis);
memset(cx,-1,sizeof cx);
memset(cy,-1,sizeof cy);
for(int i=1;i<=n;++i)
{
memset(vis,0,sizeof vis);
res+=dfs(i);
}
return res;
}
int main()
{
scanf("%d",&t);
for(int cas=1;cas<=t;++cas)
{
scanf("%d%d",&n,&m);
mx=max(n,m);
init();
for(int i=1;i<=n;++i)
{
scanf("%d",&k);
for(int j=1;j<=k;++j)
{
scanf("%d",&v);
add(i,v+mx);
}
}
hungary();
for(int i=1;i<=n;++i)
if(~cx[i])add(cx[i],i);//存在最大匹配
all=2*mx;//[1,mx][mx+1,2*mx]是实际的王子 公主
for(int i=1;i<=n;++i)
{
if(~cx[i])continue;
all++;//虚拟公主 被所有人喜欢 匹配给没有公主的王子
for(int j=1;j<=n;++j)
add(j,all);
cx[i]=all;cy[all]=i;add(all,i);
}
for(int i=mx+1;i<=mx+m;++i)
{
if(~cy[i])continue;
all++;//虚拟王子 喜欢所有公主 匹配给没有王子的公主
for(int j=mx+1;j<=mx+m;++j)
add(all,j);
cx[all]=i;cy[i]=all;add(i,all);
}
for(int i=1;i<=all;++i)
if(!dfn[i])tarjan(i);
printf("Case #%d:\n",cas);
for(int u=1;u<=n;++u)
{
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].to;
if(par[u]==par[v]&&v<=2*mx)
ans.push_back(v-mx);
}
sort(ans.begin(),ans.end());
len=ans.size();
printf("%d",len);
for(int i=0;i<len;i++)
printf(" %d",ans[i]);
ans.clear();
puts("");
}
}
return 0;
}