// 先看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个公主。且没有给出初始匹配。一个公主可以嫁给很多王子??......
// 由于n和m是不一样的，先用求得最大匹配很可能就不是完美匹配，这时候需要构造虚拟王子和虚拟公主，虚拟王子喜欢每个公主(非虚拟)，虚拟公主被每个王子(非虚拟)喜欢，然后(和poj 1904步骤一样)求一个完美匹配再建图，求SCC。
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<set> 5 using namespace std; 6 7 inline int read() { 8 char c=getchar(); int f=1,x=0; 9 while(c<‘0‘||c>‘9‘) { if(c==‘-‘)f=-1;c=getchar(); } 10 while(c>=‘0‘&&c<=‘9‘) { x=x*10+c-‘0‘;c=getchar(); } 11 return f*x; 12 } 13 14 inline void write(int a) { 15 if(a<0)putchar(‘-‘),a=-a; 16 if(a>9)write(a/10); 17 putchar(a%10+‘0‘); 18 } 19 //--------------------------------- 20 const int MAXN = 2000+5; 21 const int MAXE = 500*500; 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, m, sum; 36 int cx[MAXN], cy[MAXN]; 37 bool vis[MAXN]; 38 39 bool dfs(int u) { 40 vis[u] = true; 41 for(int i = head[u]; i != -1; i = edge[i].next) { 42 int v = edge[i].v; 43 if(!vis[v]) { 44 vis[v] = true; 45 if(!cy[v] || dfs(cy[v])) { 46 cx[u] = v; 47 cy[v] = u; 48 return true; 49 } 50 } 51 } 52 return false; 53 } 54 55 int hungry(int nm) { 56 int ans = 0; 57 for(int i = 1; i <= nm; ++i) cx[i] = cy[i] = 0; 58 for(int i = 1; i <= nm; ++i) { 59 for(int j = 1; j <= nm; ++j) vis[j] = false; 60 if(dfs(i)) ++ans; 61 } 62 return ans; 63 } 64 65 void build() { 66 sum = n+m; 67 int res = hungry(sum); 68 int xt = m-res, yt = n-res; 69 for(int i = 1; i <= xt; ++i) { 70 ++sum; 71 for(int j = n+1; j <= n+m; ++j) { 72 add(sum, j); 73 } 74 } 75 for(int i = 1; i <= yt; ++i) { 76 ++sum; 77 for(int j = 1; j <= n; ++j) { 78 add(j, sum); 79 } 80 } 81 hungry(sum); 82 for(int i = 1; i <= n+xt; ++i) add(cx[i], i); 83 for(int i = n+m+1; i <= n+m+xt; ++i) add(cx[i], i); 84 } 85 86 int cnt, scc_cnt, t; 87 int dfn[MAXN], low[MAXN], sccno[MAXN], st[MAXN]; 88 89 void Tarjan(int u) { 90 dfn[u] = low[u] = ++cnt; 91 st[++t] = u; 92 vis[u] = true; 93 for(int i = head[u]; i != -1; i = edge[i].next) { 94 int v = edge[i].v; 95 if(!dfn[v]) { 96 Tarjan(v); 97 low[u] = min(low[u], low[v]); 98 } 99 else if(vis[v]) low[u] = min(low[u], dfn[v]); 100 } 101 if(dfn[u] == low[u]) { 102 ++scc_cnt; 103 int v; 104 do { 105 v = st[t--]; 106 sccno[v] = scc_cnt; 107 vis[v] = false; 108 } while(v != u); 109 } 110 } 111 112 void solve() { 113 cnt = scc_cnt = t = 0; 114 for(int i = 1; i <= sum; ++i) dfn[i] = vis[i] = 0; 115 for(int i = 1; i <= sum; ++i) if(!dfn[i]) Tarjan(i); 116 for(int i = 1; i <= n; ++i) { 117 set<int> marry; 118 for(int j = head[i]; j != -1; j = edge[j].next) { 119 int v = edge[j].v; 120 if(v > n+m) continue; 121 if(sccno[i] == sccno[v]) marry.insert(v-n); 122 } 123 write(marry.size()); 124 for(set<int>::iterator j = marry.begin(); j != marry.end(); ++j) { 125 putchar(‘ ‘); 126 write(*j); 127 } 128 putchar(‘\n‘); 129 } 130 } 131 132 int main() { 133 int T = read(), Case = 0; 134 int nm, x; 135 while(T--) { 136 n = read(); m = read(); 137 num = 0; 138 memset(head, -1, sizeof(head)); 139 for(int i = 1; i <= n; ++i) { 140 nm = read(); 141 for(int j = 0; j != nm; ++j) { 142 x = read(); 143 add(i, x+n); 144 } 145 } 146 printf("Case #%d:\n", ++Case); 147 build(); 148 solve(); 149 } 150 return 0; 151 }
原文：https://www.cnblogs.com/pupil-xj/p/11819310.html
