题意:国王有N个儿子,每个儿子都有很多喜欢的姑娘,官员为每个王子都找了一个姑娘让他们结婚,不过国王不满意,他想知道他的每个儿子都可以和那个姑娘结婚(前提他的儿子必须喜欢那个姑娘)
分析:因为最下面一行已经给出来每个王子可以结婚的对象了,所以就不必在去求完备匹配了,直接加入反边求出来环就行了,不过注意环中的姑娘未必是王子喜欢的对象,需要再次判断一下才行。ps.第一次知道有输出输入外挂这东西,不过优化的确实很给力。
************************************************************************
#include<stdio.h>
#include<string.h>
#include<vector>
#include<algorithm>
using namespace std; const int MAXN = ; struct Edge{int v, next;}e[MAXN*];
int Head[MAXN], cnt;
int dfn[MAXN], low[MAXN], Index;
int Stack[MAXN], instack[MAXN], top;
int belong[MAXN], bnt;
int N;
bool love[][];
vector< vector <int> >ans; void InIt()
{
ans.clear();
ans.resize(MAXN); memset(love, false, sizeof(love));
memset(dfn, false, sizeof(dfn));
memset(Head, -, sizeof(Head)); cnt = Index = bnt = ;
}
void AddEdge(int u, int v)
{
e[cnt].v = v;
e[cnt].next = Head[u];
Head[u] = cnt++;
}
void Tarjan(int i)
{
int v; dfn[i] = low[i] = ++Index;
Stack[++top] = i, instack[i] = true; for(int j=Head[i]; j!=-; j=e[j].next)
{
v = e[j].v; if( !dfn[v] )
{
Tarjan(v);
low[i] = min(low[i], low[v]);
}
else if( instack[v] )
low[i] = min(low[i], dfn[v]);
} if(low[i] == dfn[i])
{
++bnt;
do
{
v = Stack[top--];
instack[v] = false;
belong[v] = bnt;
if(v > N)
ans[bnt].push_back(v-N);
}
while(i != v);
}
} int Scan() { //输入外挂
int res = , flag = ;
char ch;
if((ch = getchar()) == '-') flag = ;
else if(ch >= '' && ch <= '') res = ch - '';
while((ch = getchar()) >= '' && ch <= '')
res = res * + (ch - '');
return flag ? -res : res;
} void Out(int a) { //输出外挂
if(a < ) { putchar('-'); a = -a; }
if(a >= ) Out(a / );
putchar(a % + '');
} int main()
{
while(scanf("%d", &N) != EOF)
{
int i, v, M; InIt(); for(i=; i<=N; i++)
{
M = Scan(); while(M--)
{
v = Scan();
AddEdge(i, v+N);
love[i][v] = true;
}
} for(i=; i<=N; i++)
{
v = Scan();
AddEdge(v+N, i);
love[i][v] = true;
} for(i=; i<=N*; i++)
{
if( !dfn[i] )
Tarjan(i);
} for(i=; i<=N; i++)
{
v = belong[i]; int j, len = ans[v].size();
int a[MAXN], t=; for(j=; j<len; j++)
{
if( love[i][ ans[v][j] ] == true )
a[t++] = ans[v][j];
} sort(a, a+t); printf("%d", t);
for(j=; j<t; j++)
{
putchar(' ');
Out(a[j]);
}
printf("\n");
}
} return ; }