【bzoj3444】【最后的晚餐】【组合数学】-白红宇的个人博客

【bzoj3444】【最后的晚餐】【组合数学】

发布日期：2021-11-16 15:38:39 浏览次数：7 分类：技术文章

本文共 1213 字，大约阅读时间需要 4 分钟。

Description

【问题背景】

高三的学长们就要离开学校，各奔东西了。某班n人在举行最后的离别晚餐时，饭店老板觉得十分纠结。因为有m名学生偷偷找他，要求和自己暗恋的同学坐在一起。

【问题描述】

饭店给这些同学提供了一个很长的桌子，除了两头的同学，每一个同学都与两个同学相邻（即坐成一排）。给出所有信息，满足所有人的要求，求安排的方案总数（这个数字可能很大，请输出方案总数取余989381的值，也可能为0）。

Input

输入有m+1行，第一行有两个用空格隔开的正整数n、m，如题所示。接下来的m行，每一行有两个用空格隔开的正整数，第i行为Ai和Bi，表示Ai的暗恋对象为Bi，保证Ai互不相等。

Output

输出只有一行，这一行只有一个数字，如题所示。

Sample Input

4 2
1 2
4 3

Sample Output

8

【数据范围】
100%的数据，0＜n≤500000，1≤Ai，Bi≤n，0≤m≤n，保证没有人自恋。

题解：首先如果关系存在环或者是有一个人的暗恋数大于2一定无解。

这个连边然后dfs判断即可。

对于一个联通块肯定只有2种方案.

然后联通块之间可以全排列。

注意判断一下重边即可。

代码：

#include
    
     #include
     
      #include
      #define P 989381#define N 500010#define M 500010 using namespace std;int k,d[N],flag,cnt,point[N],next[M<<1],n,m,x,y,vis[N],t;long long ans(1);map
       
        f[N]; struct use{int st,en;}e[M<<1];void add(int x,int y){  d[x]++;next[++cnt]=point[x];point[x]=cnt;e[cnt].en=y;}void dfs(int x,int pre){  vis[x]=1;if (flag) return;  for (int i=point[x];i;i=next[i])   if (e[i].en!=pre){    if (!vis[e[i].en]) k=1,dfs(e[i].en,x);    else  flag=1;   }} int main(){  scanf("%d%d",&n,&m);  for (int i=1;i<=m;i++){    scanf("%d%d",&x,&y);if (x>y) swap(x,y);    if (!f[x][y]) add(x,y),add(y,x),f[x][y]=1;  }  for (int i=1;i<=n;i++) if (d[i]>2){cout<<0<

转载地址：https://blog.csdn.net/sunshinezff/article/details/51063423 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：【bzoj3506/1552】【robotic sort】【splay】

下一篇：【bzoj2434】【NOI2011】【阿狸的打字机】【AC自动机+dfs序+树状数组】

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！