題意：n個王子有自己喜歡的ki個公主，有n個公主，每個王子只能娶一個自己喜歡的公主且不能綠別的王子。現(xiàn)在給你一種王子娶公主的方案，并且保證這種方案是正確的。請你給出，每個王子能娶哪些公主，要求娶這些公主時，其他王子也能娶到公主。

思路：還以為是完全匹配，直接暴力匹配顯然TLE了。正解是縮點(diǎn)...我們把每個王子指向自己喜歡的公主們，然后把給定的方案中的公主指向自己嫁給的王子，然后縮點(diǎn)，同一個點(diǎn)中王子喜歡的公主都能娶。因?yàn)槊總€王子指向的肯定都是公主（至少兩個），公主指向的肯定都是王子，所以想要形成一個強(qiáng)連通圖這個圖中王子公主數(shù)量肯定是相同的，那么假如王子選擇一個自己喜歡的公主，那么這個圖中的其他的王子可以選擇其他的公主，顯然肯定能完全匹配。

代碼：

#include<set> #include<map> #include<stack> #include<cmath> #include<queue> #include<vector> #include<string> #include<cstdio> #include<cstring> #include<sstream> #include<iostream> #include<algorithm> typedef long long ll; using namespace std; const int maxn = 4000 + 10; const int MOD = 1e9 + 7; const int INF = 0x3f3f3f3f; int head[maxn], ans[maxn], tot; struct Edge{int to, next; }edge[maxn * maxn]; int low[maxn], dfn[maxn], Stack[maxn], belong[maxn]; int index, top, scc; bool instack[maxn]; void addEdge(int u, int v){edge[tot].to = v;edge[tot].next = head[u];head[u] = tot++; } void tarjan(int u){int v;low[u] = dfn[u] = ++index;Stack[top++] = u;instack[u] = true;for(int i = head[u]; i != -1; i = edge[i].next){v = edge[i].to;if(!dfn[v]){tarjan(v);if(low[u] > low[v]) low[u] = low[v];}else if(instack[v] && low[u] > dfn[v]){low[u] = dfn[v];}}if(low[u] == dfn[u]){scc++;do{v = Stack[--top];instack[v] = false;belong[v] = scc;}while(v != u);} } void solve(int n){memset(dfn, 0, sizeof(dfn));memset(instack, false, sizeof(instack));index = scc = top = 0;for(int i = 1; i <= n; i++){if(!dfn[i])tarjan(i);} } void init(){tot = 0;memset(head, -1, sizeof(head)); } int main(){int n;while(~scanf("%d", &n)){int k, tmp;init();for(int i = 1; i <= n; i++){scanf("%d", &k);while(k--){scanf("%d", &tmp);addEdge(i, tmp + n);}}for(int i = 1; i <= n; i++){scanf("%d", &tmp);addEdge(tmp + n, i);}solve(2 * n);int ret;for(int u = 1; u <= n; u++){ret = 0;for(int i = head[u]; i != -1; i = edge[i].next){int v = edge[i].to;if(belong[v] == belong[u]){ans[ret++] = v - n;}}sort(ans, ans + ret);printf("%d", ret);for(int i = 0; i < ret; i++){printf(" %d", ans[i]);}printf("\n");}}return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/KirinSB/p/10464958.html

總結(jié)

以上是生活随笔為你收集整理的POJ 1904 King's Quest（强连通图）题解的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。