Poj_1904

背景：本來(lái)是在做Voj的連通分量，做到了E（ hdu_4685 ），想到了二分圖，但是筆者只會(huì)最大匹配，但題目要求要輸出所有的最大匹配情況，想了好久都沒想出來(lái)怎么做，因?yàn)槿绻乙阎粋€(gè)最大匹配，那么就可以將公主連反向邊指向王子，然后跑tarjan，將每個(gè)強(qiáng)連通分量的王子配公主輸出即可，但是這題沒有給出最大匹配，這個(gè)還不是最坑的，因?yàn)榭梢耘芤淮巫畲笃ヅ?#xff0c;最坑的是n個(gè)王子，但是有m個(gè)公主，看到這個(gè)真的想打人，這個(gè)就真的難受了，因?yàn)槿绻腥藛紊碓趺崔k？？所以就去百度了，然后題解幾乎全部提及Poj1904，于是乎筆者就去找到了這題，這題就是筆者想的那個(gè)給出匹配的版本，所以很快A掉了，但是！！re了4發(fā)，因?yàn)橥踝庸骶?000，筆者邊集數(shù)組沒有多想，只開了兩倍，到最后一直開到10w都還是re，最后百度一看，20W起加（貌似有個(gè)204000）過的，最后數(shù)組開到26w就過去了，不得不說(shuō)這題的這個(gè)坑點(diǎn)真的是，很難過了。

題目大意：給出n個(gè)王子和他們仰慕的公主，接下來(lái)給出每個(gè)公主已經(jīng)匹配的王子（即給出一組最大匹配），輸出每個(gè)王子最多能和哪些公主匹配。

題解：對(duì)于王子仰慕的公主建邊，而題目提供的最大匹配，用于建反向邊，然后tarjan縮點(diǎn)，同一個(gè)分量里面的王子公主隨意輸出（筆者排了個(gè)序方便差錯(cuò)，忘了題目是否有要求）。

PS：今天應(yīng)該可以把hdu_4685寫出來(lái)，題解說(shuō)是要虛擬出公主和王子，容筆者仔細(xì)想想，感覺想通了實(shí)現(xiàn)應(yīng)該很快，畢竟這些點(diǎn)都挺熟悉的。

---

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <vector> using namespace std;const int N = 5005; const int M = 260000; const int INF = 0x3f3f3f3f;struct Edge {int u, v, nxt; }; Edge edge[M]; int ecnt, head[N]; int top, sum, dep; bool vis[N]; int sta[N], low[N], dfn[N], col[N]; int ans[N];void _add( int a, int b ) {edge[ecnt].u = a;edge[ecnt].v = b;edge[ecnt].nxt = head[a];head[a] = ecnt ++; }void tarjan( int u ) {sta[++top] = u;low[u] = dfn[u] = ++dep;vis[u] = 1;for ( int i = head[u]; i+1; i = edge[i].nxt ){int v = edge[i].v;if ( !dfn[v] ){tarjan(v);low[u] = min( low[u], low[v] );}else if ( vis[v] )low[u] = min( low[u], low[v] );}if ( low[u] == dfn[u] ){vis[u] = 0;col[u] = ++sum;while ( sta[top] != u ){vis[sta[top]] = 0;col[sta[top--]] = sum;}top --;} }int main() {int n;scanf("%d", &n);memset(head,-1,sizeof(head));for ( int i = 1; i <= n; i ++ ){int cn, pricn;scanf("%d", &cn);while ( cn -- ){scanf("%d", &pricn);_add( i, pricn + n );}}for ( int i = 1; i <= n; i ++ ){int pric;scanf("%d", &pric);_add( pric + n, i );}for ( int i = 1; i <= n; i ++ )if ( !dfn[i] )tarjan(i);for ( int i = 1; i <= n; i ++ ){int cnt = 0;for ( int j = head[i]; j+1; j = edge[j].nxt ){int v = edge[j].v;if ( col[i] == col[v] )ans[cnt++] = v - n;}sort(ans,ans+cnt);printf("%d", cnt);for ( int i = 0; i < cnt; i ++ )printf(" %d", ans[i]);printf("\n");}return 0; }

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

總結(jié)

以上是生活随笔為你收集整理的Graph_Master(连通分量_Poj_1904)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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