POJ 3648 Wedding(2
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>

Heiße KI -Werkzeuge

Undresser.AI Undress
KI-gestützte App zum Erstellen realistischer Aktfotos

AI Clothes Remover
Online-KI-Tool zum Entfernen von Kleidung aus Fotos.

Undress AI Tool
Ausziehbilder kostenlos

Clothoff.io
KI-Kleiderentferner

AI Hentai Generator
Erstellen Sie kostenlos Ai Hentai.

Heißer Artikel

Heiße Werkzeuge

Notepad++7.3.1
Einfach zu bedienender und kostenloser Code-Editor

SublimeText3 chinesische Version
Chinesische Version, sehr einfach zu bedienen

Senden Sie Studio 13.0.1
Leistungsstarke integrierte PHP-Entwicklungsumgebung

Dreamweaver CS6
Visuelle Webentwicklungstools

SublimeText3 Mac-Version
Codebearbeitungssoftware auf Gottesniveau (SublimeText3)

Heiße Themen

In diesem Artikel wird die Optimierung von MySQL -Speicherverbrauch in Docker untersucht. Es werden Überwachungstechniken (Docker -Statistiken, Leistungsschema, externe Tools) und Konfigurationsstrategien erörtert. Dazu gehören Docker -Speichergrenzen, Tausch und CGroups neben

Dieser Artikel befasst sich mit MySQLs Fehler "Die freigegebene Bibliotheksfehler". Das Problem ergibt sich aus der Unfähigkeit von MySQL, die erforderlichen gemeinsam genutzten Bibliotheken (.SO/.dll -Dateien) zu finden. Lösungen beinhalten die Überprüfung der Bibliotheksinstallation über das Paket des Systems m

In dem Artikel werden mithilfe der Änderungstabelle von MySQL Tabellen, einschließlich Hinzufügen/Löschen von Spalten, Umbenennung von Tabellen/Spalten und Ändern der Spaltendatentypen, erläutert.

Dieser Artikel vergleicht die Installation von MySQL unter Linux direkt mit Podman -Containern mit/ohne phpmyadmin. Es beschreibt Installationsschritte für jede Methode und betont die Vorteile von Podman in Isolation, Portabilität und Reproduzierbarkeit, aber auch

Dieser Artikel bietet einen umfassenden Überblick über SQLite, eine in sich geschlossene, serverlose relationale Datenbank. Es beschreibt die Vorteile von SQLite (Einfachheit, Portabilität, Benutzerfreundlichkeit) und Nachteile (Parallelitätsbeschränkungen, Skalierbarkeitsprobleme). C

In diesem Handbuch wird die Installation und Verwaltung mehrerer MySQL -Versionen auf macOS mithilfe von Homebrew nachgewiesen. Es betont die Verwendung von Homebrew, um Installationen zu isolieren und Konflikte zu vermeiden. Der Artikel Details Installation, Starten/Stoppen von Diensten und Best PRA

In Artikel werden die Konfiguration der SSL/TLS -Verschlüsselung für MySQL, einschließlich der Erzeugung und Überprüfung von Zertifikaten, erläutert. Das Hauptproblem ist die Verwendung der Sicherheitsauswirkungen von selbstsignierten Zertifikaten. [Charakterzahl: 159]

In Artikel werden beliebte MySQL -GUI -Tools wie MySQL Workbench und PhpMyAdmin beschrieben, die ihre Funktionen und ihre Eignung für Anfänger und fortgeschrittene Benutzer vergleichen. [159 Charaktere]
