poj1904 完美匹配+Tarjan
Time Limit: 15000MS | Memory Limit: 65536K | |
Total Submissions: 9460 | Accepted: 3497 | |
Case Time Limit: 2000MS |
Description
So the king asked his wizard to find for each of his sons the girl he liked, so that he could marry her. And the king's wizard did it -- for each son the girl that he could marry was chosen, so that he liked this girl and, of course, each beautiful girl had to marry only one of the king's sons.
However, the king looked at the list and said: "I like the list you have made, but I am not completely satisfied. For each son I would like to know all the girls that he can marry. Of course, after he marries any of those girls, for each other son you must still be able to choose the girl he likes to marry."
The problem the king wanted the wizard to solve had become too hard for him. You must save wizard's head by solving this problem.
Input
The last line of the case contains the original list the wizard had made -- N different integer numbers: for each son the number of the girl he would marry in compliance with this list. It is guaranteed that the list is correct, that is, each son likes the girl he must marry according to this list.
Output
Sample Input
4
2 1 2
2 1 2
2 2 3
2 3 4
1 2 3 4
Sample Output
2 1 2
2 1 2
1 3
1 4
题解这里
#include<vector>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=;
const int M=4e6+;
vector<int>sc[N];
vector<int>G[N];
int head[N],dfn[N],low[N],q[N];
bool instack[N],mp[][];
int tot,scnt,l,cnt;
struct node
{
int to,next;
} e[M];
void add(int u,int v)
{
e[tot].to=v;
e[tot].next=head[u];
head[u]=tot++;
}
void Tarjan(int u)
{
dfn[u]=low[u]=++cnt;
q[l++]=u;
instack[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(instack[v]&&dfn[v]<low[u]) low[u]=dfn[v];
}
if(low[u]==dfn[u])
{
++scnt;
int t;
do
{
t=q[--l];
sc[scnt].push_back(t);
instack[t]=;
}
while(t!=u);
}
}
int main()
{
int n,x,y;
while(scanf("%d",&n)!=EOF)
{
tot=scnt=cnt=l=;
memset(head,-,sizeof(head));
memset(dfn,,sizeof(dfn));
memset(mp,,sizeof(mp));
for(int i=; i<=n; ++i)
{
scanf("%d",&x);
while(x--)
{
scanf("%d",&y);
add(i,y+n);
G[i].clear();
sc[i].clear();
mp[i][y]=;
}
}
for(int i=; i<=n; ++i)
{
scanf("%d",&x);
add(x+n,i);
}
for(int i=; i<=n; ++i) if(!dfn[i]) Tarjan(i);
for(int i=; i<=scnt; ++i) sort(sc[i].begin(),sc[i].end());
for(int i=; i<=scnt; ++i)
{
int tc=upper_bound(sc[i].begin(),sc[i].end(),n)-sc[i].begin();
for(int j=; j<tc; ++j) for(int k=tc; k<(int)sc[i].size(); ++k) if(mp[sc[i][j]][sc[i][k]-n] ) G[sc[i][j]].push_back(sc[i][k]-n);
}
for(int i=; i<=n; ++i)
{
printf("%d",(int)G[i].size());
for(int j=; j<(int)G[i].size(); ++j) printf(" %d",G[i][j]);
puts("");
}
}
}
最新文章
- $\LaTeX$笔记:Section 编号方式(数字、字母、罗马)&;计数器计数形式修改
- 【ipv6惹的祸】curl 超时
- 使用ActivityManager实现进程管理
- nginx server中的server_name配置的域名在客户机上无法访问
- Android(Xamarin)之旅(四)
- 纯css3代码写九宫格效果
- 开篇 hello 内Cool超人
- [AngularJS] New in Angular 1.3 - bindToController
- Struts2使用Interceptor实现权限控制的应用实例详解
- svn up出现类似svn: Error converting entry in directory &#39;.&#39; to UTF-8问题解决
- 大神教你如何解决Linux系统80端口被占用
- Xshell 连接Linux服务器自动中断问题
- linux install Openvino
- 从Oracle数据库中查询前几个月数据时需要注意的一些问题
- 高能天气——团队Scrum冲刺阶段-Day 2
- 使用 ImageEnView 给图片加水印,及建缩略图
- NGINX如何反向代理Tomcat并且实现Session保持
- 微信小程序组件 加减号弹出框
- QTREE5 - Query on a tree V(LCT)
- .net将List序列转为Json字符串