hiho一下第133周 2-SAT·hihoCoder音乐节(2-SAT)(强连通)
2024-09-06 06:20:24
2-SAT·hihoCoder音乐节
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
hihoCoder音乐节由hihoCoder赞助商大力主办,邀请了众多嘉宾和知名乐队参与演出。
音乐会分为上午、下午两场进行,主办方指定了n首歌让乐队进行演唱。每首歌只会被演唱一次,要么在上午要么在下午。
参加音乐会的嘉宾们对于歌曲的演唱时间有一些要求。具体来说,每位嘉宾会指定两首歌曲的演唱时间(上午或者下午)。如果最后实际的演出安排中,两首歌都没有达到嘉宾的要求,那么嘉宾就会对音乐节不滿意。如嘉宾A的要求是上午《我的滑板鞋》和下午《忐忑》,而最后的演出中上午没有《我的滑板鞋》只有《忐忑》,下午没有《忐忑》只有《我的滑板鞋》,那么嘉宾A是不满意的。
音乐节主办方自然希望使所有嘉宾满意,但主办方后来发现有可能不存在一种歌曲的安排方案满足所有嘉宾,所以他们希望你判断一下这种情况是否会发生。
输入
输入第一行包含一个数字 K,代表K组数据。(K≤50)
对于每一组数据,第一行包含两个非负整数n和m(n≤100,m≤1000),代表有n首歌和m位嘉宾。
为了方便我们给予歌编号,编号分别从1 到n。接下的m行,每行都代表对应的嘉宾的喜好由一个英文字母(m或h)跟一个数字代表,如m1 代表这个评审喜欢第1首歌上午进行,而h2代表这个评审员喜欢第2首歌下午进行。
输出
对于每一组数据,输出一行,如果能满足所有嘉宾的情况,输出GOOD;否则输出BAD。
- 样例输入
-
2
3 4
m3 h1
m1 m2
h1 h3
h3 m2
2 4
h1 m2
m2 m1
h1 h2
m1 h2 - 样例输出
-
GOOD
BAD#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <time.h>
#include <string>
#include <map>
#include <stack>
#include <vector>
#include <set>
#include <queue>
#define met(a,b) memset(a,b,sizeof a)
#define pb push_back
using namespace std;
const int N=2e3+;
const int M=N*N+;
int n,m,k,s,t,tot,cut=,tim=,top=;
int head[N],vis[N];
int dfn[N],low[N],stack1[N],num[N];
struct man {
int to,next;
} edg[M];
void add(int u,int v) {
//printf("!!!%d %d\n",u,v);
edg[tot].to=v;
edg[tot].next=head[u];
head[u]=tot++;
}
void Tarjan(int u) {
int v;
low[u] = dfn[u] = ++tim;
stack1[top++] = u;
vis[u] = ;
for(int e = head[u]; e != -; e = edg[e].next) {
v = edg[e].to;
if(!dfn[v]) {
Tarjan(v);
low[u] = min(low[u], low[v]);
} else if(vis[v]) {
low[u] = min(low[u], dfn[v]);
}
}
if(low[u] == dfn[u]) {
cut++;
do {
v = stack1[--top];
num[v] = cut;
vis[v] = ;
} while(u != v);
}
}
void init(){
tot=top=cut=tim=;
met(head,-);
met(low,);
met(dfn,);met(vis,);met(num,);
}
int main() {
int t,A,B;
char a,b;
scanf("%d",&t);
while(t--){
init();
bool ok=true;
scanf("%d%d",&n,&m);
while(m--){
scanf(" %c%d %c%d",&a,&A,&b,&B);
int An=A+n;
int Bn=B+n;
if(a=='h')swap(A,An);
if(b=='h')swap(B,Bn);
add(An,B);add(Bn,A);
}
for(int i=;i<=*n;i++)if(!dfn[i])Tarjan(i);
for(int i=;i<=n;i++){
if(num[i]==num[i+n]){
ok=false;
break;
}
}
if(ok)puts("GOOD");
else puts("BAD");
}
return ;
}
最新文章
- BitMap算法应用:Redis队列滤重优化
- OC第九节——协议与代理
- PHP执行系统命令
- NBUT 1010 魔法少女(DP)
- timus 1136 Parliament(二叉树)
- SQL语句的执行顺序
- Android ActionBar的Overlay模式如何不遮盖顶部内容的问题
- IOS block 记录
- (转)Eclipse快捷键大全,导包快捷键:ctrl+Shift+/
- 跨平台C/C++集成开发环境-Code::Blocks-内置GCC
- windows7 dos修改mysql root密码
- vue项目使用 prerender-spa-plugin 预渲染
- 找bug hhh
- margin auto 实现居中,与text-align:center的区别
- Docker容器集群管理之Swarm
- cordova-ios 升级到4.4.0 无法真机跑iOS8 报错: dyld`dyld_fatal_error: ->; 0x120085088 <;+0>;: brk #0x3
- Ambiguous mapping found. Cannot map &#39;XXXController&#39; bean method
- mac下如何全量删除短信内容
- Mybaties原理图
- poj3133 Manhattan Wiring