题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1823
数据生成器：http://paste.ubuntu.com/22127360/
2-sat的裸题
如果一个评委是喜欢h1 && m3
那么为了满足该评委一定有：m1 -> m3 或 h3 -> h1
™读入那里写挫了，wa了一上午QAQ
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN = 2000+9;
int T,nxt[MAXN],to[MAXN],head[MAXN],n,m,mark[MAXN],que[MAXN],cnt;
char pat[10];
inline char Get(){
char c=getchar();
while (c != 'm' && c != 'h') c=getchar();
return c;
}
inline int read(){
char c=getchar(); int ret=0;
while (c<'0'||c>'9') c=getchar();
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret;
}
inline void AddEdge(int a, int b){
to[++T] = b; nxt[T] = head[a]; head[a] = T;
}
inline void init(){
scanf("%d%d",&n,&m); T = 0;
memset(head,0,sizeof(head));
memset(mark,0,sizeof(mark));
}
bool DFS(int w){
if (mark[w^1]) return false;
if (mark[w]) return true;
mark[w] = 1; que[++cnt] = w;
for (int i=head[w];i;i=nxt[i])
if (!DFS(to[i])) return false;
return true;
}
inline bool judge(){
for (int i=1*2;i<=n*2+1;i+=2) if (!mark[i] && !mark[i+1]) {
cnt = 0; if (DFS(i)) continue;
else {
for (int j=1;j<=cnt;j++) mark[que[j]] = 0;
cnt = 0; if (!DFS(i+1)) return false;
}
}
return true;
}
int main(){
int TT; scanf("%d",&TT);
while (TT--) {
init();
for (int i=1,a,b,ra,rb;i<=m;i++) {
pat[1] = Get(); a = ra = read()*2;
pat[4] = Get(); b = rb = read()*2;
if (pat[1] == 'm') a++; else ra++;
if (pat[4] == 'm') b++; else rb++;
AddEdge(ra,b);
AddEdge(rb,a);
}
if (judge()) printf("GOOD\n");
else printf("BAD\n");
}
return 0;
}
Major thankies for the article post.Really thank you! Want more.
Hey there! I know this is kind of off topic but I was wondering which blog platform are you using for this
site? I’m getting sick and tired of WordPress because I’ve
had problems with hackers and I’m looking at alternatives for another platform.
I would be fantastic if you could point me in the direction of a
good platform.
Hi there! I know this is kinda off topic but I was wondering which blog platform are
you using for this website? I’m getting tired of WordPress because I’ve had problems with hackers and I’m looking at
alternatives for another platform. I would be awesome if you could point me in the direction of a good platform.
I pay a visit daily some websites and websites to read content, however this web site gives quality based articles.
Hello to every , for the reason that I am genuinely eager of reading this weblog’s post to be updated regularly.
It consists of pleasant data.
Everything is very open with a clear clarification of the challenges.
It was definitely informative. Your website is useful.
Thank you for sharing!
Thanks in support of sharing such a nice idea,
article is good, thats why i have read it completely
Hi there, just became alert to your blog through Google, and found that it’s truly informative.
I’m gonna watch out for brussels. I will be grateful if you continue
this in future. Lots of people will be benefited from
your writing. Cheers!
Hello there, I found your web site by way of Google
even as looking for a related subject, your website came up, it appears to be like
good. I’ve bookmarked it in my google bookmarks.
Hello there, simply was alert to your blog via Google, and located that it’s truly informative.
I am going to be careful for brussels. I’ll be grateful in the event you continue this in future.
Lots of other people shall be benefited from your writing.
Cheers!
Valuable information. Fortunate me I discovered your web site by chance, and
I am shocked why this twist of fate didn’t came about in advance!
I bookmarked it.
I feel this is among the so much important info for me.
And i am glad studying your article. However wanna observation on few normal things, The site taste is great, the articles is in point of
fact nice : D. Good activity, cheers
Keep working ,splendid job!
I am not sure where you’re getting your information, but great topic.
I needs to spend some time learning much more or understanding more.
Thanks for wonderful info I was looking for this info for my mission.
When someone writes an paragraph he/she keeps the thought of
a user in his/her mind that how a user can know it.
Therefore that’s why this paragraph is outstdanding. Thanks!
With havin so much content and articles do you ever run into any issues of plagorism or copyright infringement?
My site has a lot of completely unique content I’ve either created myself or outsourced but it looks like a lot of
it is popping it up all over the internet without my agreement.
Do you know any techniques to help protect against content from being stolen? I’d
genuinely appreciate it.
After I originally commented I appear to have clicked the -Notify me
when new comments are added- checkbox and from now on every time
a comment is added I get four emails with the
exact same comment. Perhaps there is a means you are able to remove me from that service?
Appreciate it!
Hi there! I’m at work surfing around your blog from my new
iphone 3gs! Just wanted to say I love reading your blog and look forward to all your posts!
Carry on the fantastic work!
Pretty! This was an incredibly wonderful article. Many thanks for supplying this info.
Fantastic blog! Do you have any helpful hints for aspiring writers?
I’m hoping to start my own blog soon but I’m a little lost on everything.
Would you recommend starting with a free platform like WordPress
or go for a paid option? There are so many options out there that I’m totally overwhelmed ..
Any recommendations? Many thanks!
Normally I do not read post on blogs, however I wish to say that this write-up very pressured me to check out and do so!
Your writing style has been surprised me. Thank you, quite nice article.
Useful info. Fortunate me I discovered your site by chance, and I’m stunned
why this accident didn’t took place in advance! I bookmarked it.
I believe other website proprietors should take this site as an example , very clean and great user genial style.