Home Database Mysql Tutorial POJ 3648 Wedding(2

POJ 3648 Wedding(2

Jun 07, 2016 pm 03:48 PM

POJ 3648 Wedding(2-SAT) http://poj.org/problem?id=3648 题意: 有一对新人结婚,n-1对夫妇去参加婚.有一个很长的座子,新娘与新郎坐在座子的两边(相反).接下来n-1对夫妇就坐,其中任何一对夫妇都不能坐在同一边,且(有一些人有奸情)这些有奸情的两个人不能同时

POJ 3648 Wedding(2-SAT)

http://poj.org/problem?id=3648

题意:

        有一对新人结婚,n-1对夫妇去参加婚礼.有一个很长的座子,新娘与新郎坐在座子的两边(相反).接下来n-1对夫妇就坐,其中任何一对夫妇都不能坐在同一边,且(有一些人有奸情)这些有奸情的两个人不能同时坐在新娘对面.(只能分开做,或者都坐到新娘一边去)。对于每个输入实例,输出应该坐在新娘同一边的人编号。

分析:

        由于有n对夫妇(0号表示新婚夫妻).所以我们这里用0表示第0对的妻子,1表示第0对的丈夫. 2*i表示第i对的夫人,2*i+1表示第i对的丈夫.一共就有2*n个人了.

        然后对于每个人来说,把他分成两个节点,如果该人在做左边就mark[i*2],如果该人坐右边就mark[i*2+1].

        我令新娘直接坐左边即第0个人mark[0]=true,新郎直接坐右边即第1个人mark[1*2+1]=true.

        然后对于每对夫妻,因为他们不能在同一边,所以第i对夫妻中a= 2*i表示妻子,b=2*i+1表丈夫. 有这样的关系:

a在左边,那么b就在右边,a*2->b*2+1

a在右边,那么b就在左边,a*2+1->b*2

b在左边,那么a就在右边,b*2->a*2+1

b在右边,那么a就在左边,b*2+1->a*2

        然后对于每对有奸情的人a与b,因为它们不能同时在新娘对面(右边),所以:

a*2+1->b*2

b*2+1->a*2

        注意首先我们定了新娘(0号)在左边,新郎(第1号人)一定在右边,所以我们要先加上:

0*2+1->0*2  和 1*2->1*2+1 

这样就保证了新娘和新郎在固定的那边不动.

AC代码:

#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn = 1000*2+100;
struct TwoSAT
{
    int n;
    vector<int> G[maxn*2];
    int S[maxn*2],c;
    bool mark[maxn*2];

    bool dfs(int x)
    {
        if(mark[x^1]) return false;
        if(mark[x]) return true;
        mark[x]=true;
        S[c++]=x;
        for(int i=0;i<g if return false true void init n this->n=n;
        for(int i=0;i0) mark[S[--c]]=false;
                if(!dfs(i+1)) return false;  //注意细节,这里写成了return true;
            }
        }
        return true;
    }
}TS;
int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m)==2)
    {
        if(n==0&&m==0) break;
        TS.init(n*2);
        TS.add_clause(0,1,0,0);//新娘放左
        TS.add_clause(1,0,1,1);//新郎放右
        for(int i=1;i<n int a="i*2;" b="i*2+1;//丈夫" ts.add_clause for i="0;i<m;i++)" char s1 scanf if else printf luck return><br>
<br>


</n></g></int></algorithm></vector></cstring></cstdio>
Copy after login
Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn

Hot AI Tools

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress AI Tool

Undress images for free

Clothoff.io

Clothoff.io

AI clothes remover

Video Face Swap

Video Face Swap

Swap faces in any video effortlessly with our completely free AI face swap tool!

Hot Tools

Notepad++7.3.1

Notepad++7.3.1

Easy-to-use and free code editor

SublimeText3 Chinese version

SublimeText3 Chinese version

Chinese version, very easy to use

Zend Studio 13.0.1

Zend Studio 13.0.1

Powerful PHP integrated development environment

Dreamweaver CS6

Dreamweaver CS6

Visual web development tools

SublimeText3 Mac version

SublimeText3 Mac version

God-level code editing software (SublimeText3)

When might a full table scan be faster than using an index in MySQL? When might a full table scan be faster than using an index in MySQL? Apr 09, 2025 am 12:05 AM

Full table scanning may be faster in MySQL than using indexes. Specific cases include: 1) the data volume is small; 2) when the query returns a large amount of data; 3) when the index column is not highly selective; 4) when the complex query. By analyzing query plans, optimizing indexes, avoiding over-index and regularly maintaining tables, you can make the best choices in practical applications.

Explain InnoDB Full-Text Search capabilities. Explain InnoDB Full-Text Search capabilities. Apr 02, 2025 pm 06:09 PM

InnoDB's full-text search capabilities are very powerful, which can significantly improve database query efficiency and ability to process large amounts of text data. 1) InnoDB implements full-text search through inverted indexing, supporting basic and advanced search queries. 2) Use MATCH and AGAINST keywords to search, support Boolean mode and phrase search. 3) Optimization methods include using word segmentation technology, periodic rebuilding of indexes and adjusting cache size to improve performance and accuracy.

Can I install mysql on Windows 7 Can I install mysql on Windows 7 Apr 08, 2025 pm 03:21 PM

Yes, MySQL can be installed on Windows 7, and although Microsoft has stopped supporting Windows 7, MySQL is still compatible with it. However, the following points should be noted during the installation process: Download the MySQL installer for Windows. Select the appropriate version of MySQL (community or enterprise). Select the appropriate installation directory and character set during the installation process. Set the root user password and keep it properly. Connect to the database for testing. Note the compatibility and security issues on Windows 7, and it is recommended to upgrade to a supported operating system.

Difference between clustered index and non-clustered index (secondary index) in InnoDB. Difference between clustered index and non-clustered index (secondary index) in InnoDB. Apr 02, 2025 pm 06:25 PM

The difference between clustered index and non-clustered index is: 1. Clustered index stores data rows in the index structure, which is suitable for querying by primary key and range. 2. The non-clustered index stores index key values ​​and pointers to data rows, and is suitable for non-primary key column queries.

What are some popular MySQL GUI tools (e.g., MySQL Workbench, phpMyAdmin)? What are some popular MySQL GUI tools (e.g., MySQL Workbench, phpMyAdmin)? Mar 21, 2025 pm 06:28 PM

Article discusses popular MySQL GUI tools like MySQL Workbench and phpMyAdmin, comparing their features and suitability for beginners and advanced users.[159 characters]

How do you handle large datasets in MySQL? How do you handle large datasets in MySQL? Mar 21, 2025 pm 12:15 PM

Article discusses strategies for handling large datasets in MySQL, including partitioning, sharding, indexing, and query optimization.

MySQL: Simple Concepts for Easy Learning MySQL: Simple Concepts for Easy Learning Apr 10, 2025 am 09:29 AM

MySQL is an open source relational database management system. 1) Create database and tables: Use the CREATEDATABASE and CREATETABLE commands. 2) Basic operations: INSERT, UPDATE, DELETE and SELECT. 3) Advanced operations: JOIN, subquery and transaction processing. 4) Debugging skills: Check syntax, data type and permissions. 5) Optimization suggestions: Use indexes, avoid SELECT* and use transactions.

The relationship between mysql user and database The relationship between mysql user and database Apr 08, 2025 pm 07:15 PM

In MySQL database, the relationship between the user and the database is defined by permissions and tables. The user has a username and password to access the database. Permissions are granted through the GRANT command, while the table is created by the CREATE TABLE command. To establish a relationship between a user and a database, you need to create a database, create a user, and then grant permissions.

See all articles