这道题很神奇,尤其是背景最神奇,国王竟然能有2000个儿子。
首先,看完题后第一感觉跟二分匹配有关系,结果最后给了一组完美匹配,于是,如果男的喜欢女的就连一条单向边过去,最后那组表示结婚的,就让女的连一条单向边给她丈夫,然后我们观察这个图,如果一个女的能跟这个男的结婚,首先男的必须喜欢她,然后通过这条边过去,到女的结点,然后从女的结点出发,必然能回到这个男的结点处,而且,如果这个女的不是这个男的妻子,那么她必然是从某男结点,然后到达这个男的妻子的结点,然后回到这个男的结点,这就表明,这个男的可以选择另外一个女的做妻子而不会导致某个男的没有妻子选。
那么,这就形成了一个环,而且是男女结点交替,就转化为了强连通分量的求解。
在一个男的喜欢的所有女的中,如果女的跟他是同一个强连通分量,就表示符合要求
另外 这题的输入输出量非常大,我用Kosaraju算法,不加输入输出外挂的话用了10S,加完之后直接就600ms了,直接进第一版
貌似tarjan更快
/*
ID: sdj22251
PROG: subset
LANG: C++
*/
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define LOCA
#define MAXN 4005
#define INF 100000000
#define eps 1e-7
using namespace std;
struct Edge
{
int v, next;
}edge[100 * MAXN], revedge[100 * MAXN];
int head[MAXN], revhead[MAXN], e, visited[MAXN];
int order[MAXN], cnt, id[MAXN];
int n, m;
void init()
{
e = 0;
memset(head, -1, sizeof(head));
memset(revhead, -1, sizeof(revhead));
}
void insert(const int &x, const int &y)
{
edge[e].v = y;
edge[e].next = head[x];
head[x] = e;
revedge[e].v = x;
revedge[e].next = revhead[y];
revhead[y] = e;
e++;
}
int in()
{
char ch;
int a = 0;
while((ch = getchar()) == ' ' || ch == '\n');
a += ch - '0';
while((ch = getchar()) != ' ' && ch != '\n')
{
a *= 10;
a += ch - '0';
}
return a;
}
void out(int a)
{
if(a >= 10)out(a / 10);
putchar(a % 10 + '0');
}
void readdata()
{
int t, v;
for(int i = 1; i <= n; i++)
{
t = in();
while(t--)
{
v = in();
insert(i, v + n);
}
}
for(int i = 1; i <= n; i++)
{
v= in();
insert(v + n, i);
}
}
void dfs(int u)
{
visited[u] = 1;
for(int i = head[u]; i != -1; i = edge[i].next)
{
int v = edge[i].v;
if(!visited[v])
dfs(v);
}
order[cnt++] = u;
}
void dfs_rev(int u)
{
visited[u] = 1;
id[u] = cnt;
for(int i = revhead[u]; i != -1; i = revedge[i].next)
{
int v = revedge[i].v;
if(!visited[v])
dfs_rev(v);
}
}
void Kosaraju()
{
init();
readdata();
memset(visited, 0, sizeof(visited));
cnt = 0;
for(int i = 1; i <= 2 * n; i++)
{
if(!visited[i])
dfs(i);
}
memset(visited, 0, sizeof(visited));
cnt = 0;
for(int i = 2 * n - 1; i >= 0; i--)
{
if(!visited[order[i]])
{
cnt++;
dfs_rev(order[i]);
}
}
for(int u = 1; u <= n; u++)
{
cnt = 0;
int ans[MAXN];
for(int i = head[u]; i != -1; i = edge[i].next)
{
int v = edge[i].v;
if(id[u] == id[v])
{
ans[cnt++] = v - n;
}
}
sort(ans, ans + cnt);
out(cnt);
for(int i = 0; i < cnt; i++)
{
putchar(' ');
out(ans[i]);
}
puts("");
}
}
int main()
{
while(scanf("%d", &n) != EOF)
{
Kosaraju();
}
return 0;
}
分享到:
相关推荐
POJ2186-Popular Cows ...【Tarjan+极大强连通分量+缩点】 解题报告+AC代码 http://hi.csdn.net/!s/BGDH68 附:我所有的POJ解题报告链接 . http://blog.csdn.net/lyy289065406/article/details/6642573
北大POJ1426-Find The Multiple【BFS+同余模】 解题报告+AC代码
北大POJ1691-Painting A Board 【拓扑+DFS】 解题报告+AC代码
北大POJ2513-Colored Sticks【TrieTree+MergeSet+EulerPath】 解题报告+AC代码
北大POJ1002-487-3279【Hash+Qsort】 解题报告+AC代码
POJ3177-Redundant Paths 【Tarjan-边双连通分量-缩点】 解题报告+AC代码+测试数据 http://hi.csdn.net/!s/GPAY6Z 附:我所有的POJ解题报告链接 . http://blog.csdn.net/lyy289065406/article/details/6642573
北大POJ中级搜索全部练习【解题报告+AC代码】
POJ3352-Road Construction 【Tarjan-边双连通分量-缩点】 解题报告+AC代码 http://hi.csdn.net/!s/0T8UO5 附:我所有的POJ解题报告链接 . http://blog.csdn.net/lyy289065406/article/details/6642573
2505 2521 2538 2546 2551 2590 2593 2601 2665 2680 2739 2752 2761 2762 2777 2800 2891 2893 2992 3030 3041 3132 3159 3187 3204 3270 3277 3281 3297 3321 3414 3436 3461 3650 3663 3664 3672 3740
北大POJ3733-Changing Digits【DFS+强剪枝】 解题报告+AC代码
北大POJ3373-Changing Digits【DFS+强剪枝】 解题报告+AC代码
北大POJ3009-Curling 2.0【DFS+Vector+回溯+剪枝】 解题报告+AC代码
北大POJ3026-Borg Maze【BFS+Prim】 解题报告+AC代码
北大POJ初级-所有题目AC代码+解题报告
北大POJ1936-All in All 解题报告+AC代码
北大POJ1027-The Same Game 解题报告+AC代码
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
北大POJ3349-Snowflake Snow Snowflakes 解题报告+AC代码
北大POJ2262-Goldbach's Conjecture 解题报告+AC代码
北大POJ2388-Who's in the Middle 解题报告+AC代码