// 先看poj 1904 (hdu 4685是它的升级版)
// poj 1904 题意：给n个王子和n个公主，输入王子喜欢的公主，王子只能娶他自己喜欢的人，而公主可以嫁给任何王子(只要那个王子喜欢他)，且一个公主只能嫁给一个人。已知每个王子至少能取一个公主(n个王子都能娶到自己喜欢的公主)。输入： n个王子 、下面n行列出每个王子喜欢的公主、巫师给出的一组娶妻方案(一个完美匹配方案)。1 <= N <= 2000,每个王子喜欢公主的数量总和<=200000.
// 问：输出每个王子可以娶公主的最大数量和这些公主的列表(升序)。(在每个王子最大方案中，王子任意娶其中一个公主，其他王子不会单身)
// 解法：先建图，首先如果王子u喜欢公主v 建一条e(u->v)。 题目给出了一组完美匹配，对于这个匹配，王子u娶公主v，建一条e(v->u)。然后对于这个建出的图，求它的强连通分量，一个王子可以取和他在同一个强连通中的所有公主(这就是他能娶的最大人数)。
// 分析这个图：后来加的完美匹配的边e(v->u)表示公主v被王子u娶了，对于原先e(u->v)表示王子u喜欢公主v。 对于某个强连通，王子和公主的数量是相等的，如果某个王子u变心(本来完美匹配给他一个公主x)想娶某个公主v，那么就有一个边 e(u->v), 设想u现在想娶v，那么娶v的王子就要换一个人娶(当然是娶她另外一个喜欢的)，而那个公主也被一个王子娶了，那么那个王子就要换一个已经被娶的公主......直到某个王子被迫娶到了第一个变心的王子丢弃的公主(这个公主x有一条边又指向了抛弃她的王子)。这样在这个图中每个王子都可以变心，娶完美匹配外的一个公主，然后那些王子被迫娶完美匹配外的其他公主。这样就能形成了一个强连通。不行的话盯着画的图加一直看就懂了。
// 输入输出量都很大,scanf 和 printf 都能超时。需要用到'外挂'输入/输出。所谓'外挂'就是自己写个函数用getchar()和putchar()输入/输出
// poj 1904
1 #include<cstdio> 2 #include<set> 3 #define read(n) n = read_n() 4 #define rep(i, n) for(int i=0;i!=n;++i) 5 #define rep1(i, n) for(int i=1;i<=n;++i) 6 using namespace std; 7 8 inline int read_n() { 9 char c=getchar();int x=0,f=1; 10 while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} 11 while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} 12 return x*f; 13 } 14 inline void put(int a) { 15 if(a<0){putchar('-');a=-a;} 16 if(a>9)put(a/10); 17 putchar(a%10+'0'); 18 } 19 // ----------------------------------------------------- 20 const int MAXN = 4000+5; 21 const int MAXE = 202000+5; 22 23 int num; 24 int head[MAXN]; 25 struct node { 26 int v, next; 27 } edge[MAXE]; 28 29 inline void add(int x, int y) { 30 edge[num].v = y; 31 edge[num].next = head[x]; 32 head[x] = num++; 33 } 34 35 int n; 36 int cnt, scc_cnt, t; 37 int dfn[MAXN], low[MAXN], st[MAXN], sccno[MAXN]; 38 bool vis[MAXN]; 39 40 void Tarjan(int u) { 41 dfn[u] = low[u] = ++cnt; 42 vis[u] = true; 43 st[++t] = u; 44 for(int i = head[u]; i != -1; i = edge[i].next) { 45 int v = edge[i].v; 46 if(!dfn[v]) { 47 Tarjan(v); 48 low[u] = min(low[u], low[v]); 49 } 50 else if(vis[v]) low[u] = min(low[u], dfn[v]); 51 } 52 if(dfn[u] == low[u]) { 53 ++scc_cnt; 54 int v; 55 do { 56 v = st[t--]; 57 sccno[v] = scc_cnt; 58 vis[v] = false; 59 } while(v != u); 60 } 61 } 62 63 void solve() { 64 cnt = scc_cnt = t = 0; 65 rep1(i, 2*n) vis[i] = dfn[i] = 0; 66 rep1(i, 2*n) if(!dfn[i]) Tarjan(i); 67 rep1(i, n) { 68 set<int> marry; 69 for(int j = head[i]; j != -1; j = edge[j].next) { 70 int v = edge[j].v; 71 if(sccno[i] == sccno[v]) marry.insert(v-n); 72 } 73 put(marry.size()); 74 for(set<int>::iterator j = marry.begin(); j != marry.end(); ++j) { 75 putchar(' '); 76 put(*j); 77 } 78 putchar('\n'); 79 } 80 } 81 82 int main() { 83 while(scanf("%d", &n) == 1) { 84 //read(n); 85 num = 0; 86 rep1(i, n*2) head[i] = -1; 87 int nm, x; 88 rep1(i, n) { 89 read(nm); 90 rep(j, nm) { 91 read(x); 92 add(i, x+n); 93 } 94 } 95 rep1(i, n) read(x), add(x+n, i); 96 solve(); 97 } 98 return 0; 99 }
//-------------------------------------------------------
// 题面和上一题一样。不同的是： n个王子和m个公主。且没有给出初始匹配。一个公主可以嫁给很多王子