poj3648
2024-09-24 12:06:50
poj3648
题意
有一对新人结婚,n-1对夫妇去参加婚礼.有一个很长的座子,新娘与新郎坐在座子的两边(相反).接下来n-1对夫妇就坐,其中任何一对夫妇都不能坐在同一边,且(有一些人有奸情)这些有奸情的两个人不能同时坐在新娘对面.(只能分开做,或者都坐到新娘一边去)。对于每个输入实例,输出应该坐在新娘同一边的人编号。
分析
弄清楚题意后,建图比较简单(对立关系比较单一),注意新娘连边到新郎,保证新郎一定在对面,且新郎也可能有奸情。
code
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
const int INF = 1e9;
const int MAXN = 2e4 + 5;
int vis[MAXN], flag[MAXN];
vector<int> G[MAXN], rG[MAXN];
vector<int> vs;
int n, m;
void addedge(int x, int y)
{
G[x].push_back(y);
rG[y].push_back(x);
}
void dfs(int u)
{
vis[u] = 1;
for(int i = 0; i < G[u].size(); i++)
{
int v = G[u][i];
if(!vis[v]) dfs(v);
}
vs.push_back(u);
}
void rdfs(int u, int k)
{
vis[u] = 1; flag[u] = k;
for(int i = 0; i < rG[u].size(); i++)
{
int v = rG[u][i];
if(!vis[v]) rdfs(v, k);
}
}
int scc()
{
vs.clear();
memset(vis, 0, sizeof vis);
for(int i = 0; i < n; i++)
if(!vis[i]) dfs(i);
memset(vis, 0, sizeof vis);
int k = 0;
for(int i = vs.size() - 1; i >= 0; i--)
if(!vis[vs[i]]) rdfs(vs[i], k++);
return k;
}
bool judge()
{
int N = n;
n = 2 * n;
scc();
for(int i = 0; i < 2 * N; i++)
if(flag[i] == flag[i ^ 1]) return false;
return true;
}
int main()
{
while(~scanf("%d%d", &n, &m) && (n + m))
{
memset(G, 0, sizeof G);
memset(rG, 0, sizeof rG);
addedge(0, 1); // 新娘 -> 新郎
for(int i = 0; i < m; i++)
{
int u, v;
char c1, c2;
scanf("%d%c%d%c", &u, &c1, &v, &c2);
u *= 2; v *= 2;
if(c1 == 'h') u ^= 1;
if(c2 == 'h') v ^= 1;
addedge(u, v ^ 1);
addedge(v, u ^ 1);
}
if(!judge()) puts("bad luck");
else
{
for(int i = 2; i < n; i += 2)
{
if(flag[i] > flag[i ^ 1])
printf("%dh", i / 2);
else printf("%dw", i / 2);
if(i >= n - 2) puts("");
else printf(" ");
}
}
}
return 0;
}
最新文章
- Clean Old Kernels on CentOS
- springmvc配置多视图 - tiles, velocity, freeMarker, jsp
- 隐式调用 Intent 大全, 很全
- Tomcat负载均衡配置-未完成
- springMVC+MyBatis+Spring 整合(2)
- Cocos2dx项目启程一 之 封装属于我的精灵类
- XXX系统发展综述(SSH+Jquery EasyUI)
- temp--达州银行
- css图片的相关操作
- 【腾讯海纳】系统未发布时如何获取获取property_id在本地进行测试?
- 如何让vba与java的TripleDES算法通用
- springboot的几种启动方式
- linux的必知必会规则
- C# 运行中 Lua 语言脚本
- 安卓程序代写 网上程序代写[原]BluetoothAdapter解析
- [USACO06DEC] 牛奶模式Milk Patterns
- vue 学习报错 Newline required at end of file but not found
- php方法重载
- 20个PHP程序性能优化的方法
- UltraISO制作启动盘及提取U盘为ISO镜像
热门文章
- T-SQL语句中的转换函数
- JAVA常用集合源码解析系列-ArrayList源码解析(基于JDK8)
- python——面向对象进阶
- Struts2框架的基本使用
- BZOJ 1266: [AHOI2006]上学路线route
- jade模板引擎简明用法
- Transform java future into completable future 【将 future 转成 completable future】
- 阿里云主机试用之自建站点和ftp上传所遇的2个问题
- [原创]ssget过滤动态块的方式
- 【2017-05-05】timer控件、三级联动、帐号激活权限设置