LUOGU P1407 [国家集训队]稳定婚姻

传送门

解题思路

让所有夫妇之间连男到女的边,所有情人之间连女到男的边,然后用$tarjan$,如果对于一对夫妻在强连通分量里,那么就是不稳定的,因为他们可以绕一圈。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<map>

using namespace std;
const int MAXN = 8005;
const int MAXM = 40005;

int n,m,cnt,head[MAXN],tot,to[MAXM],nxt[MAXM];
int dfn[MAXN],low[MAXN],num,stk[MAXN],top,col[MAXN],col_num;
bool vis[MAXN];
string s1,s2;
map<string,int> mp;

inline void add(int bg,int ed){
    to[++cnt]=ed,nxt[cnt]=head[bg],head[bg]=cnt;
}

void tarjan(int x){
    dfn[x]=low[x]=++num;vis[x]=1;stk[++top]=x;
    for(register int i=head[x];i;i=nxt[i]){
        int u=to[i];
        if(!dfn[u]) {tarjan(u);low[x]=min(low[x],low[u]);}
        else if(vis[u]) low[x]=min(dfn[u],low[x]);
    }
    if(dfn[x]!=low[x]) return;
    col[x]=++col_num;vis[x]=0;
    while(stk[top]!=x){
        vis[stk[top]]=0;
        col[stk[top--]]=col_num;
    }top--;
}

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        cin>>s1>>s2;add(tot+1,tot+2);
        mp[s1]=++tot;mp[s2]=++tot;
    }
    scanf("%d",&m);
    for(int i=1;i<=m;i++)
        cin>>s1>>s2,add(mp[s2],mp[s1]);
    for(int i=1;i<=2*n;i++) if(!dfn[i]) tarjan(i);
    for(int i=1;i<=n;i++)
        puts(col[i<<1]==col[(i<<1)-1]?"Unsafe":"Safe");
    return 0;
}

原文地址:https://www.cnblogs.com/sdfzsyq/p/9773738.html

时间: 10-11

LUOGU P1407 [国家集训队]稳定婚姻的相关文章

国家集训队2011 happiness

[试题来源] 2011中国国家集训队命题答辩 [问题描述] 高一一班的座位表是个n*m的矩阵,经过一个学期的相处,每个同学和前后左右相邻的同学互相成为了好朋友.这学期要分文理科了,每个同学对于选择文科与理科有着自己的喜悦值,而一对好朋友如果能同时选文科或者理科,那么他们又将收获一些喜悦值.作为计算机竞赛教练的scp大老板,想知道如何分配可以使得全班的喜悦值总和最大. [输入格式] 第一行两个正整数n,m.接下来是六个矩阵第一个矩阵为n行m列 此矩阵的第i行第j列的数字表示座位在第i行第j列的同学

[国家集训队2010]小Z的袜子

★★★   输入文件:hose.in   输出文件:hose.out   简单对比 时间限制:1 s   内存限制:512 MB [题目描述] 作为一个生活散漫的人,小Z每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿.终于有一天,小Z再也无法忍受这恼人的找袜子过程,于是他决定听天由命…… 具体来说,小Z把这N只袜子从1到N编号,然后从编号L到R(L 尽管小Z并不在意两只袜子是不是完整的一双,甚至不在意两只袜子是否一左一右,他却很在意袜子的颜色,毕竟穿两只不同色的袜子会很尴尬. 你的任务便

【bzoj2140】: 稳定婚姻 图论-tarjan

[bzoj2140]: 稳定婚姻 哎..都是模板题.. 一眼看过去 哇 二分图哎 然后发现好像并不能匈牙利算法 自己xjb画两张图,发现二分图左向右连配偶的边,然后右向左连交往过的边 然后如果Bi Gi在同一个强连通分量里面就一定可以在Bi Gi离婚以后再增广一次 最开始用map维护一下名字就好了 1 /* http://www.cnblogs.com/karl07/ */ 2 #include <cstdlib> 3 #include <cstdio> 4 #include &l

BZOJ 2038: [2009国家集训队]小Z的袜子(hose)

2038: [2009国家集训队]小Z的袜子(hose) Time Limit: 20 Sec  Memory Limit: 259 MBSubmit: 7676  Solved: 3509[Submit][Status][Discuss] Description 作为一个生活散漫的人,小Z每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿.终于有一天,小Z再也无法忍受这恼人的找袜子过程,于是他决定听天由命……具体来说,小Z把这N只袜子从1到N编号,然后从编号L到R(L 尽管小Z并不在意两只

uva 1175 Ladies&#39; Choice (稳定婚姻问题)

uva 1175 Ladies' Choice Background Teenagers from the local high school have asked you to help them with the organization of next year?s Prom. The idea is to find a suitable date for everyone in the class in a fair and civilized way. So, they have or

[补档][国家集训队2011]单选错位

题目 gx和lc去参加noip初赛,其中有一种题型叫单项选择题,顾名思义,只有一个选项是正确答案. 试卷上共有n道单选题,第i道单选题有ai个选项,这ai个选项编号是1,2,3,-,ai,每个选项成为正确答案的概率都是相等的.lc采取的策略是每道题目随机写上1-ai的某个数作为答案选项,他用不了多少时间就能期望做对sigma(1/ai)道题目.gx则是认认真真地做完了这n道题目,可是等他做完的时候时间也所剩无几了,于是他匆忙地把答案抄到答题纸上,没想到抄错位了:第i道题目的答案抄到了答题纸上的第

【BZOJ】2038: [2009国家集训队]小Z的袜子(hose)

[算法]莫队 [题解] BZOJ 2038 2009国家集训队 小Z的袜子(hose) 莫队算法 莫队--讲稿? 施工中--

cogs 1901. [国家集训队2011]数颜色

Cogs 1901. [国家集训队2011]数颜色 ★★★   输入文件:nt2011_color.in   输出文件:nt2011_color.out   简单对比时间限制:0.6 s   内存限制:512 MB [试题来源] 2011中国国家集训队命题答辩 [问题描述] 墨墨购买了一套N支彩色画笔(其中有些颜色可能相同),摆成一排,你需要回答墨墨的提问.墨墨会像你发布如下指令:1. Q L R代表询问你从第L支画笔到第R支画笔中共有几种不同颜色的画笔.2. R P Col 把第P支画笔替换为

【BZOJ 2039】 2039: [2009国家集训队]employ人员雇佣 (最小割)

2039: [2009国家集训队]employ人员雇佣 Time Limit: 20 Sec  Memory Limit: 259 MBSubmit: 1511  Solved: 728 Description 作为一个富有经营头脑的富翁,小L决定从本国最优秀的经理中雇佣一些来经营自己的公司.这些经理相互之间合作有一个贡献指数,(我们用Ei,j表示i经理对j经理的了解程度),即当经理i和经理j同时被雇佣时,经理i会对经理j做出贡献,使得所赚得的利润增加Ei,j.当然,雇佣每一个经理都需要花费一定

(算法)稳定婚姻匹配

题目: 婚介所登记了N位男孩和N位女孩,每个男孩都对N个女孩的喜欢程度做了排序,每个女孩都对N个男孩的喜欢程度做了排序,你作为月老,能否给出稳定的牵手方案? 稳定的定义:如果男孩i和女孩a牵手,但男孩i对女孩b更喜欢,而女孩b的男朋友j拼不过男孩i,则没有力量阻碍男孩i和女孩b的私奔,这即是不稳定的. 思路: 1962 年,美国数学家 David Gale 和 Lloyd Shapley 发明了一种寻找稳定婚姻的策略.不管男女各有多少人,不管他们各自的偏好如何,应用这种策略后总能得到一个稳定的婚