关键词:
Description
Input
Output
Sample Input
input | output |
---|---|
3 4 1 2 2 3 1 4 |
Yes 2 3 4 |
6 4 1 2 1 3 1 4 2 3 2 4 3 4 |
No |
题意:给出n对点a,b 要求从没对点中选出一个,且最终选出的点n个数不能存在相同的。输入数据满足每种数最多出现3次,最少出现1次
思路:第i对点的编号2*i, 2*i+1, 因为每个数最多出现3次,那么完全可以枚举每个数,然后相同的数之间的编号连一条边,表示这两个编号不能同时选,这样跑完twosat就能得到一个满足情况的解或无解。
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <queue> #include <stack> #include <cstdlib> #include <map> #include <set> #include <cmath> using namespace std; const int N = 2e6 + 100; struct Edge { int to, nex; }e[N]; int head[N], tot; void init() { tot = 0; memset(head, -1, sizeof head); } void add(int u, int v) { e[tot].to = v; e[tot].nex = head[u]; head[u] = tot++; } int Low[N], DFN[N], Stack[N], Belong[N]; int Index, top; int scc; bool Instack[N]; int num[N]; void Tarjan(int u) { int v; Low[u] = DFN[u] = ++Index; Stack[top++] = u; Instack[u] = true; for(int i = head[u]; ~i; i = e[i].nex) { v = e[i].to; if(!DFN[v]) { Tarjan(v); if(Low[u] > Low[v]) Low[u] = Low[v]; }else if(Instack[v] && Low[u] > DFN[v]) Low[u] = DFN[v]; } if(Low[u] == DFN[u]) { scc++; do { v = Stack[--top]; Instack[v] = false; Belong[v] = scc; num[scc]++; }while(v != u); } } bool solvable(int n) { memset(DFN, 0, sizeof DFN); memset(Instack, false, sizeof Instack); memset(num, 0, sizeof num); Index = scc = top = 0; for(int i = 0; i < n; ++i) if(!DFN[i]) Tarjan(i); for(int i = 0; i < n; i += 2) { if(Belong[i] == Belong[i ^ 1]) return false; } return true; } queue<int> q1, q2; vector<vector<int> >dag; int vis[N]; int indeg[N]; int cf[N]; void solve(int n) { dag.assign(scc+1, vector<int>()); memset(indeg, 0, sizeof indeg); memset(vis, 0, sizeof vis); for(int u = 0; u < n; ++u) { for(int i = head[u]; ~i; i = e[i].nex) { int v = e[i].to; if(Belong[u] != Belong[v]) { dag[ Belong[v] ].push_back(Belong[u]); indeg[ Belong[u] ]++; } } } for(int i = 0; i < n; i += 2) { cf[ Belong[i] ] = Belong[i ^ 1]; cf[ Belong[i ^ 1] ] = Belong[i]; } while(!q1.empty()) q1.pop(); while(!q2.empty()) q2.pop(); for(int i = 1; i <= scc; ++i) if(indeg[i] == 0) q1.push(i); while(!q1.empty()) { int u = q1.front(); q1.pop(); if(vis[u] == 0) { vis[u] = 1; vis[ cf[u] ] = 0; } int sz = dag[u].size(); for(int i = 0; i < sz; ++i) { indeg[ dag[u][i] ]--; if(indeg[ dag[u][i] ] == 0) q1.push(dag[u][i]); } } } int r[N]; vector<int> g[N]; int main() { #ifdef LOCAL freopen("in", "r", stdin); #endif int n, m; while(~scanf("%d%d", &m, &n)) { init(); int tot = 0; int u, v; for(int i = 0; i < m; ++i) { scanf("%d%d", &u, &v); r[tot++] = u; r[tot++] = v; g[u].push_back(2 * i); g[v].push_back(2 * i + 1); } for(int i = 1; i <= n; ++i) { int sx = g[i].size(); for(int j1 = 0; j1 < sx; ++j1) { for(int j2 = j1 + 1; j2 < sx; ++j2) { int v1 = g[i][j1]; int v2 = g[i][j2]; add(v1, v2 ^ 1); add(v2, v1 ^ 1); } } } if(solvable(2 * m)) { solve(2 * m); puts("Yes"); for(int i = 0; i < m; ++i) { if(vis[ Belong[2 * i] ]) printf("%d ", r[2 * i + 1]); else printf("%d ", r[2 * i]); } }else puts("No"); } return 0; }
hdu2089不要62
不要62TimeLimit:1000/1000MS(Java/Others) MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):30114 AcceptedSubmission(s):10603ProblemDescription杭州人称那些傻乎 查看详情
数位dphdu2089不要62
http://acm.hdu.edu.cn/showproblem.php?pid=2089【AC】1#include<bits/stdc++.h>2usingnamespacestd;3typedeflonglongll;4constintmaxn=1e6+2;5intdp[10][10];6intdigit[10];7intcnt;8intans;9intn,m;10boolche 查看详情
洛谷p2089烤鸡
P2089烤鸡 题目背景猪猪hanke得到了一只鸡题目描述猪猪Hanke特别喜 查看详情
hdoj2089数位dp
链接:http://acm.hdu.edu.cn/showproblem.php?pid=2089题意:给你一个区间,问你这个区间有多少个数字不包含4和62代码:31inta[20];32intdp[20][2];3334intdfs(intpos,intpre,intsta,boollimit){35if(pos==-1)return1;36if(!limit&&dp[pos][ 查看详情
ural-1901spaceelevators
题目:NowadaysspaceshipsareneverlaunchedfromtheEarth‘ssurface.ThereisahugespaceportplacedinthegeostationaryorbitandconnectedtotheEarthwithcarbonnanotubecables.Peopleandcargoaredeliveredtotheorbitbyelevat 查看详情
ural2020trafficjaminflowertown
2020.TrafficJaminFlowerTownTimelimit:1.0secondMemorylimit:64MBHavingreturnedfromSunCity,Dunnotoldallhisfriendsthateveryshortymayhaveapersonalautomobile.Immediatelyafterthatsomanycitizenstookafancyofbe 查看详情
hdu2089不要62
不要62TimeLimit:1000/1000MS(Java/Others) MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):44575 AcceptedSubmission(s):16546 ProblemDescrip 查看详情
hdu2089不要62
不要62TimeLimit:1000/1000MS(Java/Others) MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):39220 AcceptedSubmission(s):14260ProblemDescription杭州人称那些傻乎 查看详情
ural1424minibus
MinibusTimelimit:1.0secondMemorylimit:64MBBackgroundMinibusdriverSergeyA.Greedsonhasbecometotallyfamousforhisphenomenalgreediness.Heclaimedtimeandagainthatheheldhimselfinreadinesstothrottlehisbrothera 查看详情
ural1855tradeguildsoferathia
TradeGuildsofErathiaTimelimit:2.0secondMemorylimit:64MBThecontinentofAntagarichwascolonizedslowly.LongagoitsnorthernpartwasinhabitedbytheelvesofAvlee.Later,thehotsoutherndesertofBracadawasoccupiedbyth 查看详情
hdu2089不要62
不要62 HDU-2089 杭州人称那些傻乎乎粘嗒嗒的人为62(音:laoer)。 杭州交通管理局经常会扩充一些的士车牌照,新近出来一个好消息,以后上牌照,不再含有不吉利的数字了,这样一来,就可以消除个别的士司机... 查看详情
ural2016magicandscience
2016.MagicandScienceTimelimit:1.0secondMemorylimit:64MBScientistswhospecializeinwitchcrafthaverecentlydiscoveredanewelementaryparticlecalledamagion.Studyingthelawsofmagions’movement,agroupofthre 查看详情
ural2021scarilyinteresting!
2021.Scarilyinteresting!Timelimit:1.0secondMemorylimit:64MBThisyearatMonstersUniversityitisdecidedtoarrangeScareGames.AttheGamesallcampusgathersatthestadiumstands,andtheScareprogramstudentsdivideintot 查看详情
[ural1519]formula1
[URAL1519]Formula1试题描述Regardlessofthefact,thatVologdacouldnotgetrightstoholdtheWinterOlympicgamesof20**,itiswell-known,thatthecitywillconductoneoftheFormula1events.Surely,forsuchanimportantthinganewra 查看详情
ural1118.nontrivialnumbers
1118.NontrivialNumbersTimelimit:2.0secondMemorylimit:64MB SpecialistsofSKBKonturhavedevelopedauniquecryptographicalgorithmforneedsofinformationprotectionwhiletransmittingdataovertheInternet.Thema 查看详情
ural2015zhenyamovesfromthedormitory
2015.ZhenyamovesfromthedormitoryTimelimit:1.0secondMemorylimit:64MBAftermovingfromhisparents’placeZhenyahasbeenlivingintheUniversitydormitoryforamonth.However,hegotprettytiredofthecurfewtimeandq 查看详情
ural2017bestofabadlot
2017.BestofabadlotTimelimit:1.0secondMemorylimit:64MBAcruiselinerhasn’tmovedawayfromthelandevenforthreemileswhenitbecameapparentthatsomebodyhasdrownedoneofthestewardsintheswimmingpool.Thecaptain 查看详情
[hdu2089]不要62
[HDU2089]不要62试题描述杭州人称那些傻乎乎粘嗒嗒的人为62(音:laoer)。杭州交通管理局经常会扩充一些的士车牌照,新近出来一个好消息,以后上牌照,不再含有不吉利的数字了,这样一来,就可以消除个别的士司机和乘客的... 查看详情