首页 > 其他分享 >[COCI2016-2017#5] Ronald

[COCI2016-2017#5] Ronald

时间:2023-07-13 19:46:17浏览次数:41  
标签:航线 int COCI2016 Ronald kmax Output Input 2017 include

Problem

一个国家的 \(N\) 个城市通过双向航线相连。

规定一次操作为:

  • 选定其中一个城市
  • 开设该城市到其它所有城市的航线,同时取消该城市的原有航线

请问是否存在一种操作方式,使得每两个城市之间都存在直达航线(操作次数不限)。

\(2 \le N \le 1000\),\(0 \le M \lt \dfrac{N(N-1)}{2}\)。

Input

第一行,一个整数 \(N\),表示城市的数量。

第二行,一个整数 \(M\),表示初始的航线数量。

接下来的 \(M\) 行,每行两个不相等的整数,表示该航线连接的两个城市。

Output

若存在符合题意的操作方式,则输出 DA。否则输出 NE

Sample

Input 1

2
0

Output 1

DA

Input 2

3
2
1 2
2 3

Output 2

NE

Input 3

4
2
1 3
2 4

Output 3

DA

Solution

对于一个节点,容易发现只有操作奇数次和偶数次两种不同的状态。简化一下就是不操作和只操作一次两种情况。

于是可以考虑将每个点拆成两个点分别表示选和不选,然后建边跑并查集判是否为二分图即可。

如果原图两点间有边,两点要么都不反转,要么都反转;如果原图两点间没有边,两点间有且只有一点反转。

如果最后存在一个点使得该点拆出来的两个点属于同一个连通块,说明矛盾,否则有解。

代码:

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

const int kmax = 2005;

int n, m;
bool e[kmax][kmax];
int f[kmax];

int F(int x) {
  return f[x] == x ? x : f[x] = F(f[x]);
}

void Merge(int x, int y) {
  x = F(x), y = F(y);
  f[x] = y;
}

int main() {
  cin >> n >> m;
  for (int i = 1; i <= n << 1; i++) { // 两倍节点
    f[i] = i;
  }
  for (int i = 1, x, y; i <= m; i++) {
    cin >> x >> y;
    e[x][y] = e[y][x] = 1;
  }
  for (int i = 1; i <= n; i++) {
    for (int j = i + 1; j <= n; j++) {
      if (e[i][j]) { // 两点之间有边
        Merge(i, j); // 都不操作
        Merge(i + n, j + n); // 都操作
      } else {
        Merge(i, j + n); 
        Merge(i + n, j); // 只操作其中一个点
      }
    }
  }
  for (int i = 1; i <= n; i++) {
    if (F(i) == F(i + n)) { // 属于同一连通块
      cout << "NE";  // 矛盾
      return 0;
    }
  }
  cout << "DA";
  return 0;
}

标签:航线,int,COCI2016,Ronald,kmax,Output,Input,2017,include
From: https://www.cnblogs.com/ereoth/p/17551932.html

相关文章

  • CODE FESTIVAL 2017 Final J 题解
    problem&blog。萌萌点分治,积累个trick/qq。对于完全图\((V,E)\),将\(E\)分成\(E_1,E_2,\cdots,E_k\)(\(E_1\cupE_2\cup\cdots\cupE_k=E\))。对每个边集求MST,得到新边集\(E_1^{'},E_2^{'},\cdots,E_k^{'}\),再求MST。最终剩下的边集,等同于原边集的MST。......
  • 题解 P8648【[蓝桥杯 2017 省 A] 油漆面积】
    怎么题解区全是扫描线,还有个\(O(n^3)\)暴力老哥。为防止误导新人,给个理论上稳过的\(O(n^2)\)解法。二维前缀和可以处理若干次单点加,最后若干次矩形查的问题。将其差分,即可处理若干次矩形加,最后若干次单点查的问题。于是我们使用差分将所有矩形加上,然后做一遍二维前缀和,即......
  • [LOJ 6029]「雅礼集训 2017 Day1」市场 题解
    这道题恶心之处在于区间向下取整。这里给出两种思路:区间覆盖做法如果最大值和最小值向下取整后相等,则对此区间进行区间覆盖。我考场写的是这个,但是码错了,加上习惯不好,\(100\to64\),再加上烦了弱智错误,\(64\to9\),不给出代码。差值相等做法注意到相邻两数的向下取整的差值不......
  • [LOJ 6030]「雅礼集训 2017 Day1」矩阵 题解
    首先不难想到一个贪心,就是先填出一个全黑的行,然后再用其填黑列。而且在其中“填出一个全黑的行步数”我们应该最小化。这个贪心的正确性证明如下:必要性:填黑列的必要条件为有一个全黑的行。充分性:“填黑列的步数”就是“非全黑列的数量”。显然,如果填出一个全黑的行的过程中......
  • log4j反序列化漏洞(CVE-2017-5645)
    Log4j漏洞复现基础知识:Apache:开放源码的网页服务器ApacheLog4j:apache的一个开源项目,java下最流行的日志输入工具,控制每一条日志的输出格式。Log4j版本:2.8.1漏洞编号:CVE-2017-5645环境搭建:vulhub里的log4j已开启在4712端口会开启一个TCPserver漏洞验证:查看4712端口是否开启这里直......
  • 【jenkins】CVE-2017-1000353
    0x01漏洞原理enkins未授权远程代码执行漏洞,允许攻击者将序列化的JavaSignedObject对象传输给JenkinsCLI处理,反序列化ObjectInputStream作为Command对象,这将绕过基于黑名单的保护机制,导致代码执行。 0x02影响版本 所有Jenkins主版本均受到影响(包括<=2.56版本)所有Jen......
  • LOJ#6077. 「2017 山东一轮集训 Day7」逆序对题解
    考虑朴素dp,令\(f_{i,j}\)为\(1\simi\)排列有\(j\)个逆序对的排列数。有转移方程:\[f_{i,j}=\sum_{k=0}^{i-1}f_{i-1,j-k}\]特殊地,我们定义\(j<0\)的\(f_{i,j}\)为\(0\)。定义\(\displaystyleF_i(x)=\sum_{j=0}^{\infty}f_{i,j}x^j\),有\(\displaystyleF_{i}(x)=......
  • 吴恩达-斯坦福CS229机器学习课程-2017(秋)最新课程分享
    吴恩达主讲的机器学习-2017年秋季课程已经开课啦,今天跟大家分享这套课程。课程介绍本课程主要介绍机器学习和统计模式识别相关的知识。内容主要包括:监督学习(生成/判别学习,参数/非参数学习,神经网络,支持向量机);无监督学习(聚类,维数规约,核方法);学习理论(偏差/方差权衡;VC理论;大边缘概率......
  • NC24048 [USACO 2017 Jan P]Promotion Counting
    题目链接题目题目描述Thecowshaveonceagaintriedtoformastartupcompany,failingtorememberfrompastexperiencethatcowsmaketerriblemanagers!Thecows,convenientlynumbered1…N(\(1\leqN\leq100,000\)),organizethecompanyasatree,withco......
  • P5025 SNOI2017 炸弹
    P5025SNOI2017炸弹不难看出本题是可以转化为图论模型的:建立\(n\)个点代表\(n\)个炸弹,如果第\(i\)个炸弹能直接引爆第\(j\)个炸弹,就连边\(i\toj\)。这样的图论模型很好地刻画了原题中引爆的传递性,题意中第\(i\)个炸弹能直接/间接引爆第\(j\)个炸弹直接等价于......