P3513 [POI2011]KON-Conspiracy

    • 0通过
    • 33提交
  • 题目提供者 洛谷
  • 评测方式 云端评测
  • 标签 2-SAT 构造 POI 2011 高性能
  • 难度 尚无评定
  • 时空限制 1000ms / 512MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    Hostile Bitotia launched a sneak attack on Byteotia and occupied a significant part of its territory.

    The King of Byteotia, Byteasar, intends to organise resistance movement in the occupied area.

    Byteasar naturally started with selecting the people who will form the skeleton of the movement.

    They are to be partitioned into two groups:

    the conspirators who will operate directly in the occupied territory, and the support group that will operate inside free Byteotia.

    There is however one issue - the partition has to satisfy the following conditions:

    Every pair of people from the support group have to know each other - this will make the whole group cooperative and efficient.

    The conspirators must not know each other.

    None of the groups may be empty, i.e., there has to be at least one conspirator and at least one person in the support group.

    Byteasar wonders how many ways there are of partitioning selected people into the two groups.

    And most of all, whether such partition is possible at all.

    As he has absolutely no idea how to approach this problem, he asks you for help.

    给定一张无向图,要求你把图中的每个点染成红色或蓝色,使得红色的点形成一个团,蓝色的点形成一个独立集

    输入输出格式

    输入格式:

    The first line of the standard input holds one integer $n$ ($2\le n\le 5000$), denoting the number of people engaged in forming the resistance movement.

    These people are numbered from 1 to $n$ (for the sake of conspiracy!).

    The $n$ lines that follow describe who knows who in the group.

    The $i$-th of these lines describes the acquaintances of the person $i$ with a sequence of integers separated by single spaces.

    The first of those numbers, $k_i$ ($0\le k_i\le n-1$), denotes the number of acquaintances of the person $i$.

    Next in the line there are $k_i$ integers $a_{i,1},a_{i,2},\cdots,a_{i,k_i}$ - the numbers of $i$'s acquaintances.The numbers $a_{i,j}$ are given in increasing order and satisfy $1\le a_{i,j}\le n$,$a_{i,j}\ne i$. You may assume that if $x$ occurs in the sequence $a_i$ (i.e., among $i$'s acquaintances), then also $i$ occurs in the sequence $a_x$(i.e., among $x$'s acquaintances).

    输出格式:

    In the first and only line of the standard output your program should print out one integer:

    the number of ways to partition selected people into the conspirators and the support group.

    If there is no partition satisfying aforementioned conditions, then 0 is obviously the right answer.

    输入输出样例

    输入样例#1: 复制
    4
    2 2 3
    2 1 3
    3 1 2 4
    1 3
    输出样例#1: 复制
    3

    说明

    给定一张无向图,要求你把图中的每个点染成红色或蓝色,使得红色的点形成一个团,蓝色的点形成一个独立集

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。