首页 > 代码库 > UESTC 898 方老师和缘分 --二分图匹配+强连通分量

UESTC 898 方老师和缘分 --二分图匹配+强连通分量

2024-07-08 06:57:59   223人阅读

这题原来以为是某种匹配问题，后来好像说是强连通的问题。

做法：建图，每个方老师和它想要的缘分之间连一条有向边，然后，在给出的初始匹配中反向建边，即如果第i个方老师现在找到的是缘分u，则建边u->i。这样求出所有的强连通分量，每个强连通分量中方老师和缘分的数目一定是相等的，所以每个方老师一定可以找到与他在同一个强连通分量里的缘分，因为强连通分量中每个点都是可达的，某个方老师找到了其强连通分量中的非原配点，则该原配缘分一定可以在强连通分量中找到"新欢"。可以画个图看看。

由于要构造非二分图，缘分的编号从n+1开始，到2n。

代码：

#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <vector>#include <queue>#include <stack>#define Mod 1000000007using namespace std;#define N 200007std::vector<int> G[4005];int low[4005],dfn[4005];int instk[4005],bel[4005];int n,Time,cnt,res;stack<int> stk;int ans[2005];void Tarjan(int u){    low[u] = dfn[u] = ++Time;    stk.push(u);    instk[u] = 1;    for(int i=0;i<G[u].size();i++)    {        int v = G[u][i];        if(!dfn[v])        {            Tarjan(v);            low[u] = min(low[u],low[v]);        }        else if(instk[v])            low[u] = min(low[u],dfn[v]);    }    if(low[u] == dfn[u])    {        cnt++;        int v;        do        {            v = stk.top();            stk.pop();            instk[v] = 0;            bel[v] = cnt;        }while(u != v);    }}void init(){    memset(G,0,sizeof(G));    memset(instk,0,sizeof(instk));    memset(bel,-1,sizeof(bel));    memset(low,0,sizeof(low));    memset(dfn,0,sizeof(dfn));    Time = cnt = 0;    while(!stk.empty())        stk.pop();}int main(){    int i,j,u,v,k;    while(scanf("%d",&n)!=EOF)    {        init();        for(i=1;i<=n;i++)        {            scanf("%d",&k);            while(k--)            {                scanf("%d",&v);                G[i].push_back(v+n);            }        }        for(i=1;i<=n;i++)        {            scanf("%d",&v);            G[v+n].push_back(i);        }        for(i=1;i<=n;i++)        {            if(!dfn[i])                Tarjan(i);        }        for(u=1;u<=n;u++)        {            k = 0;            for(i=0;i<G[u].size();i++)            {                v = G[u][i];                if(bel[u] == bel[v])                    ans[k++] = v-n;            }            sort(ans,ans+k);            printf("%d",k);            for(i=0;i<k;i++)                printf(" %d",ans[i]);            printf("\n");        }    }    return 0;}
View Code

 


联系
我们