BZOJ2140_稳定婚姻_KEY

题目传送门

暴力直接对于每个点跑一遍二分图匹配，能拿四十分。

然而我们考虑正解。

对于一对Couple我们建♂->♀的一条边，对于一对曾经有恋情的情侣我们建♀->♂的一条边。

跑Tarjan缩点。

判断每一对Couple，如果在同一个强连通分量里，他们就不稳定（即能通过曾经有恋情的关系跑回来）。

code：

/**************************************************************

    Problem: 2140

    User: yekehe

    Language: C++

    Result: Accepted

    Time:936 ms

    Memory:2232 kb

****************************************************************/

#include <cstdio>

#include <map>

#include <string>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

string S1,S2;

map<string,int>MP;

int N,M;

struct list{

    int head[],nxt[],To[];

    int cnt;

    void clear(){

        memset(head,-,sizeof head);

        memset(nxt,-,sizeof nxt);

        cnt=;

    }

    void add(int x,int y)

    {

        To[cnt]=y;

        nxt[cnt]=head[x];

        head[x]=cnt;

        cnt++;

    }

}W;

int DFN[],LOW[],stack[],top,nt,vis[],cot;

int clo[];

void tarjan(int x)

{

    DFN[x]=LOW[x]=++nt;

    stack[++top]=x;

    vis[x]=;

        for(int i=W.head[x];i!=-;i=W.nxt[i]){

            if(!DFN[W.To[i]]){

                tarjan(W.To[i]);

                LOW[x]=min(LOW[x],LOW[W.To[i]]);

            }

            else if(vis[W.To[i]])LOW[x]=min(LOW[x],DFN[W.To[i]]);

        }

    if(DFN[x]==LOW[x]){

        cot++;

        while(stack[top]!=x)clo[stack[top]]=cot,vis[stack[top--]]=;

        clo[stack[top]]=cot,vis[stack[top--]]=;

    }

}

int main()

{

    //freopen("x.txt","r",stdin);

    scanf("%d\n",&N);

    W.clear();

    register int i,j;

    int now=;

        for(i=;i<=N;i++){

            cin>>S1>>S2;

            if(!MP[S1])MP[S1]=++now;

            if(!MP[S2])MP[S2]=MP[S1]+N;

            W.add(MP[S1],MP[S2]);

        }

    scanf("%d\n",&M);

        for(i=;i<=M;i++){

            cin>>S1>>S2;

            W.add(MP[S2],MP[S1]);

        }

        for(i=;i<=N*;i++){

            if(!DFN[i])tarjan(i);

        }

        for(i=;i<=N;i++){

            if(clo[i]==clo[i+N])puts("Unsafe");

            else puts("Safe");

        }

    return ;

}