UVALive 7334 Kernel Knights (dfs)
Kernel Knights
题目链接:
http://acm.hust.edu.cn/vjudge/contest/127407#problem/K
Description
Jousting is a medieval contest that involves people on horseback trying to strike each other with wooden
lances while riding at high speed. A total of 2n knights have entered a jousting tournament — n knights
from each of the two great rival houses. Upon arrival, each knight has challenged a single knight from
the other house to a duel.
A kernel is defined as some subset S of knights with the following two properties:
• No knight in S was challenged by another knight in S.
• Every knight not in S was challenged by some knight in S.
Given the set of the challenges issued, find one kernel. It is guaranteed that a kernel always exists.
Input
The input file contains several test cases, each of them as described below.
The first line contains an integer n (1 ≤ n ≤ 100000) — the number of knights of each house. The
knights from the first house are denoted with integers 1 through n, knights from the second house with
integers n + 1 through 2n.
The following line contains integers f1, f2, . . ., fn — the k-th integer fk is the index of the knight
challenged by knight k (n + 1 ≤ fk ≤ 2n).
The following line contains integers s1, s2 , . . ., sn — the k-th integer sk is the index of the knight
challenged by knight n + k (1 ≤ sk ≤ n).
Output
For each case, output the indices of the knights in the kernel on a single line. If there is more than one
solution, you may output any one.
Sample Input
4
5 6 7 7
1 3 2 3
Sample Output
1 2 4 8
##题意:
有两队骑士各n人,每位骑士会挑战对方队伍的某一个位骑士. (可能相同)
要求找出一个集合S,使得:(任意满足条件即可)
集合S中的骑士不会互相挑战.
每个集合外的骑士必定会被集合S内的某个骑士挑战.
##题解:
一开始看题有点懵比,题目的两层要求绕得有点糊涂.
在模拟样例的过程中发现,有些点是必须在S中的,而有些必须在S外,有些是不固定的.
首先,如果某个骑士没有被人挑战,那么他一定要位于S中. (反之他在集合外的话,就违背了条件2).
然后,如果某个骑士被确定在S中时,那么他的挑战对象一定要在S外. (反之违背条件1).
若某个骑士i被多个人挑战,那么要先对这些挑战者逐一进行上述判断,若某个挑战者被确定在S外,那么说明能使骑士i满足条件2的挑战者少了一个(等同于少了一个挑战者). 若所有挑战者都在S外,那么i一定在S内.
一开始觉得上述条件不够充分,特别是存在多个挑战者时,考虑会不会存在某个挑战者无法确定而导致i确定不了.
考虑无法确定的情况:
首先一定是成对出现,若只出现一个,那么由上述判据一定能够确定它.
比如样例中的15(互相挑战),上述判据就无法确定. 这时候可以推断1和5只要任意一个在集合S内都满足情况.
直接用dfs或bfs搜状态即可,从入度为0的点开始,若某点的父结点被确定在S外,则将该点的入度减少1.
##代码:
``` cpp
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define LL long long
#define eps 1e-8
#define maxn 201000
#define mod 100000007
#define inf 0x3f3f3f3f
#define mid(a,b) ((a+b)>>1)
#define IN freopen("in.txt","r",stdin);
using namespace std;
int reach[maxn];
int mp[maxn];
bool vis[maxn];
int ans[maxn];
void dfs(int cur) {
vis[cur] = 1;
if(vis[mp[cur]]) return;
if(ans[cur] == 1) { // in;
ans[mp[cur]] = -1;
dfs(mp[cur]);
return;
}
reach[mp[cur]]--; // out;
if(!reach[mp[cur]]) {
ans[mp[cur]] = 1;
dfs(mp[cur]);
}
}
int main(int argc, char const *argv[])
{
//IN;
int n;
while(scanf("%d", &n) != EOF)
{
memset(reach, 0, sizeof(reach));
for(int i=1; i<=2*n; i++) {
int x; scanf("%d", &x);
mp[i] = x;
reach[x]++;
}
memset(vis, 0, sizeof(vis));
memset(ans, 0, sizeof(ans));
for(int i=1; i<=2*n; i++) {
if(!vis[i] && !reach[i]) {
ans[i] = 1;
dfs(i);
}
}
vector<int> p; p.clear();
for(int i=1; i<=2*n; i++) {
if(ans[i] == -1) continue;
if(ans[i] == 1) p.push_back(i);
else if(i <= n) p.push_back(i);
}
int sz = p.size();
for(int i=0; i<sz; i++) {
printf("%d%c", p[i], i==sz-1?'\n':' ');
}
}
return 0;
}
最新文章
- CSS3 @media 查询
- Android 常用操作
- ExpressQuantumGrid4的cxGrid的一些使用方法和经验
- grep 相关
- ASP.NET 使用 System.Web.Script.Serialization 解析 JSON (转)
- poj 3260 The Fewest Coins
- asp.net中生成缩略图并添加版权实例代码
- 获取客户端IP地址 via C#
- 我眼中的 Oracle 性能优化
- Java中遍历Map的常用方法
- CSS基础语法
- AdaBoostRegressor
- 【收藏】8段JQuery处理表单的代码片段,很实用
- Android初级教程通过简要分析“土司”源码,来自实现定义土司理论探讨
- 面试题之C# 内存管理与垃圾回收
- UNDO(二)
- 【mmall】递归查询子节点并排重
- JSONObject基本内容(三)
- Socket网络编程--网络爬虫(2)
- svn断开重连,避免重建工作空间
热门文章
- Drawable(5)关于从资源文件构造的Drawable不显示
- JAVA的核心概念:接口(interface)
- TCSRM 591 div2(1000)(dp)
- 418. Sentence Screen Fitting
- poj 2777 Count Color(线段树 区间更新)
- bzoj2794
- UVa 11732 (Tire树) ";strcmp()"; Anyone?
- UrlRewriter.dll伪静态实现二级域名泛解析
- apache开源项目 -- VXQuery
- sharepoint2010 创建自定义列表