【tarjan】BZOJ2140-稳定婚姻

又名NTR的故事

【题目大意】

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

【思路】

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

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

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

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

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<map>

 #include<vector>

 #include<stack>

 using namespace std;

 map<string,int> Name;

 const int MAXN=+;

 int n,m;

 int cnt,col,dfn[MAXN*],low[MAXN*],instack[MAXN*],tar[MAXN*];

 vector<int> E[MAXN*];

 stack<int> S;

 void addedge(int u,int v){E[u].push_back(v);}

 void tarjan(int u)

 {

     low[u]=dfn[u]=++cnt;

     S.push(u);

     instack[u]=;//不要忘记了这两句

     for (int i=;i<E[u].size();i++)

     {

         int v=E[u][i];

         if (!instack[v])

         {

             tarjan(v);

             low[u]=min(low[u],low[v]);

         }

         else if (instack[v]==) low[u]=min(low[u],dfn[v]);

     }

     if (low[u]==dfn[u])

     {

         ++col;

         while (S.top()!=u)

         {

             tar[S.top()]=col,instack[S.top()]=;

             S.pop();

         }

         tar[u]=col,instack[u]=;

         S.pop();

     }

 }

 void init()

 {

     scanf("%d",&n);

     for (int i=;i<=n;i++)

     {

         char wife[],husband[];

         scanf("%s%s",wife,husband);

         Name[wife]=i;

         Name[husband]=i+n;

         addedge(i,i+n);

     }

     scanf("%d",&m);

     for (int i=;i<=m;i++)

     {

         char Exgf[],Exbf[];

         scanf("%s%s",Exgf,Exbf);

         int exgf=Name[Exgf],exbf=Name[Exbf];

         addedge(exbf,exgf);

     }

 }

 void solve()

 {

     cnt=col=;

     while (!S.empty()) S.pop();

     memset(instack,,sizeof(instack));

     for (int j=;j<=*n;j++) if (!instack[j]) tarjan(j);

     for (int i=;i<=n;i++)

         if (tar[i]==tar[i+n]) puts("Unsafe");

             else puts("Safe");

 }

 int main()

 {

     init();

     solve();

     return ;

 }

巴特西

【tarjan】BZOJ2140-稳定婚姻

最新文章

热门文章