UVa 359 Sex Assignments And Breeding Experiments

题目描述

每个人都知道家谱的图示表示。在这些“图片”中，使用点和线来表示家庭结构和家庭间的关系。例如，如果MMM和FFF是三个孩子（两个男孩和一个女孩）的父母，图形如下所示。

很容易想到大量的此类图形。有些可以表示家谱，有些则不能。你的任务是描述那些可以表示家谱的图形的特征。

为简化问题，我们假设处理的是一个完全由双性繁殖（MMM和FFF）特征化的种群。如果通过对种群成员进行适当的性别分配，图形能够表示理论上可能发生的繁殖实验结果，则称该图形是sexy（性感的），否则是not sexy。

你需要编写一个程序来检查任意有向图，判断它是否为sexy。

注意：

• 有向边x→yx \to yx→y表示xxx是yyy的父母
• 每个个体通常恰好有两个父母
• 每个个体不能有两个同性别父母，也不能有两个以上的父母
• 繁殖实验不会无限延伸到过去；总会达到某个点，其中种群成员的一个或两个父母是未知的（即没有父母的节点）
• 假定个体的出生在时间上是顺序的

输入格式

输入包含一系列图形描述，格式如下：

• 第一行：两个整数nnn（节点数）和mmm（有向边数）
• 接下来mmm行：每行两个整数xxx、yyy，表示从节点xxx到yyy的一条有向边

输入以文件结束符（EOF\texttt{EOF}EOF）结束。

输出格式

对于输入文件中的每个图形，输出以下语句之一：

• Graph number i is sexy
• Graph number i is not sexy

其中iii是图形在输入文件中的编号。

样例输入

5 6 1 3 2 3 1 4 2 4 1 5 2 5 3 3 1 2 2 3 3 1

样例输出

Graph number 1 is sexy Graph number 2 is not sexy

题目分析

问题的本质

这是一个有向图约束满足问题。给定一个有向图，需要判断是否存在一种给每个节点分配性别（M\texttt{M}M或F\texttt{F}F）的方式，使得：

1. 每条边表示“父母-子女”关系（xxx是yyy的父母）
2. 每个节点最多有两个父节点（入度 ≤ 2）
3. 如果一个节点有两个父节点，它们的性别必须不同（一个MMM，一个FFF）
4. 图必须是无环的（DAG\texttt{DAG}DAG），因为出生顺序要求时间上的先后关系

约束条件总结

设每个节点iii有一个布尔变量xix_ixi​，表示性别（例如000表示MMM，111表示FFF）：

1. 入度约束：每个节点的入度≤2≤ 2≤2
2. 性别异或约束：如果节点iii有两个父节点aaa和bbb，则xa≠xbx_a \neq x_bxa​=xb​（即xa⊕xb=1x_a \oplus x_b = 1xa​⊕xb​=1）
3. 无环性：图中不能有有向环（因为出生顺序不能形成循环依赖）

问题分解

1. 检查入度：每个节点入度≤2≤ 2≤2
2. 检查DAG\texttt{DAG}DAG：图中不能有环
3. 2-SAT\texttt{2-SAT}2-SAT可满足性：对于有两条入边的节点，它们的父节点性别必须不同，形成xa≠xbx_a \neq x_bxa​=xb​的约束。这是一个典型的2-SAT\texttt{2-SAT}2-SAT问题。

2-SAT\texttt{2-SAT}2-SAT建模

对于约束xa≠xbx_a \neq x_bxa​=xb​，等价于：

• (xa∨xb)∧(¬xa∨¬xb)(x_a \lor x_b) \land (\neg x_a \lor \neg x_b)(xa​∨xb​)∧(¬xa​∨¬xb​)

在2-SAT\texttt{2-SAT}2-SAT中，每个变量有两个文字：xxx（真）和¬x\neg x¬x（假）。约束(a∨b)(a \lor b)(a∨b)转化为两条蕴含边：

• ¬a→b\neg a \to b¬a→b
• ¬b→a\neg b \to a¬b→a

对于xa≠xbx_a \neq x_bxa​=xb​，即(xa∨xb)∧(¬xa∨¬xb)(x_a \lor x_b) \land (\neg x_a \lor \neg x_b)(xa​∨xb​)∧(¬xa​∨¬xb​)：

• 从¬xa\neg x_a¬xa​到xbx_bxb​
• 从¬xb\neg x_b¬xb​到xax_axa​
• 从xax_axa​到¬xb\neg x_b¬xb​
• 从xbx_bxb​到¬xa\neg x_a¬xa​

参考代码

// Sex Assignments and Breeding Experiments// UVa ID: 359// Verdict: Accepted// Submission Date: 2018-05-04// UVa Run Time: 0.060s//// 版权所有（C）2018，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;boolsexy;vector<int>color,degree,dfn,low,scc;intdfstime,cscc;vector<vector<int>>edges,parents;// edges: 原图, parents: 父节点列表stack<int>s;// Tarjan 算法求强连通分量voidtarjan(intu){dfn[u]=low[u]=++dfstime;s.push(u);for(autov:edges[u]){if(!dfn[v])tarjan(v),low[u]=min(low[u],low[v]);elseif(!scc[v])low[u]=min(low[u],dfn[v]);}if(dfn[u]==low[u]){++cscc;while(true){intv=s.top();s.pop();scc[v]=cscc;if(u==v)break;}}}// DFS 检查是否有环（DAG）voiddfs(intu){if(!sexy)return;color[u]=0;// 正在访问for(autov:edges[u])if(color[v]==-1)dfs(v);elseif(color[v]==0)// 发现环sexy=false;color[u]=1;// 访问完成}intmain(intargc,char*argv[]){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);intcases=0,x,y,n,m;while(cin>>n>>m){// 初始化edges.assign(n,vector<int>());parents.assign(n,vector<int>());degree.assign(n,0);sexy=true;// 读取边for(inti=1;i<=m;i++){cin>>x>>y;x--,y--;edges[x].push_back(y);degree[y]++;// 入度不能超过 2if(degree[y]>2)sexy=false;parents[y].push_back(x);}// 检查 DAGif(sexy){color.assign(n,-1);for(inti=0;i<n;i++)if(color[i]==-1)dfs(i);}// 2-SAT 检查if(sexy){// 构建 2-SAT 蕴含图，共 2n 个节点dfstime=0,cscc=0;while(!s.empty())s.pop();edges.assign(2*n,vector<int>());dfn.assign(2*n,0);low.assign(2*n,0);scc.assign(2*n,0);// 对于有两条入边的节点，添加 x_p1 != x_p2 约束for(inti=0;i<n;i++)if(parents[i].size()>1){intb1=parents[i][0],b2=parents[i][1];// x_b1 != x_b2 转换为蕴含边edges[b1+n].push_back(b2);edges[b2+n].push_back(b1);edges[b2].push_back(b1+n);edges[b1].push_back(b2+n);}// 求强连通分量for(inti=0;i<2*n;i++)if(!dfn[i])tarjan(i);// 检查是否有矛盾for(inti=0;i<n;i++)if(scc[i]==scc[i+n]){sexy=false;break;}}cout<<"Graph number "<<++cases<<" is ";cout<<(sexy?"sexy":"not sexy")<<'\n';}return0;}