首页 > 代码库 > 【tarjan】BZOJ2140-稳定婚姻

【tarjan】BZOJ2140-稳定婚姻

2024-08-13 12:53:59   225人阅读

又名NTR的故事

【题目大意】

n对夫妻Bi和Gi。若某男Bi与某女Gj曾经交往过，他们有私奔的可能性。不妨设Bi和Gj旧情复燃，进而Bj会联系上了他的初恋情人Gk，以此递推。若在Bi和Gi离婚的前提下，这2n个人最终依然能够结合成n对情侣，那么我们称婚姻i为不安全的，否则婚姻i就是安全的。问n对夫妻的婚姻分别是安全的吗？

【思路】

第一反应是匈牙利算法，但是太过于暴力了，过不了。

我们把夫妻中女方连向男方，旧情中男方连向女方。可以得出结论：如果该有向图的强连通分量中，夫妻双方在同一个强连通分量里，那么他们的婚姻是不安全的，否则他们的婚姻是安全的。

为什么呢？如果在同一个强连通分量中，显然可以连出一个增广路，相当于匈牙利算法可以跑，那么必定是能形成新的n对情侣的。

如果不在一个强连通分量中，可以理解为匈牙利算法不能调整了（具体原因见匈牙利算法），那么必定不能形成新的n对情侣。

 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<map> 6 #include<vector> 7 #include<stack> 8 using namespace std; 9 map<string,int> Name;10 const int MAXN=4000+50;11 int n,m;12 int cnt,col,dfn[MAXN*2],low[MAXN*2],instack[MAXN*2],tar[MAXN*2];13 vector<int> E[MAXN*2];14 stack<int> S;15 16 void addedge(int u,int v){E[u].push_back(v);}17 18 void tarjan(int u)19 {20     low[u]=dfn[u]=++cnt;21     S.push(u);22     instack[u]=1;//不要忘记了这两句23     for (int i=0;i<E[u].size();i++)24     {25         int v=E[u][i];26         if (!instack[v])27         {28             tarjan(v);29             low[u]=min(low[u],low[v]);30         }31         else if (instack[v]==1) low[u]=min(low[u],dfn[v]);32     }33     34     if (low[u]==dfn[u])35     {36         ++col;37         while (S.top()!=u)38         {39             tar[S.top()]=col,instack[S.top()]=2;40             S.pop();41         }42         tar[u]=col,instack[u]=2;43         S.pop();44     }45 }46 47 void init()48 {49     scanf("%d",&n);50     for (int i=1;i<=n;i++)51     {52         char wife[15],husband[15];53         scanf("%s%s",wife,husband);54         Name[wife]=i;55         Name[husband]=i+n;56         addedge(i,i+n);57     }58     scanf("%d",&m);59     for (int i=1;i<=m;i++)60     {61         char Exgf[15],Exbf[15];62         scanf("%s%s",Exgf,Exbf);63         int exgf=Name[Exgf],exbf=Name[Exbf];64         addedge(exbf,exgf);65     }66 }67 68 void solve()69 {70     cnt=col=0;71     while (!S.empty()) S.pop();72     memset(instack,0,sizeof(instack));73     for (int j=1;j<=2*n;j++) if (!instack[j]) tarjan(j);74     for (int i=1;i<=n;i++)75         if (tar[i]==tar[i+n]) puts("Unsafe");76             else puts("Safe");77 }78 79 int main()80 {81     init();82     solve();83     return 0;84 }

 

【tarjan】BZOJ2140-稳定婚姻


联系
我们