【Henu ACM Round#16 C】Graph and String
string and 16 round Graph ACM Henu
2023-09-14 09:03:45 时间
【链接】 我是链接,点我呀:)
【题意】
【题解】
根据题意:先明确以下规则: 1.如果两个点之间没有边,那么这两个点只能是a或c,且不能相同 2.如果两个点之间有边,那么他们之间的差的绝对值<=1那么对于点i,如果它和所有的点都相连了,那么就干脆把他变成b.
这样其他点无论选什么都和它没有关系,其他点选什么都可以了
接下里,找到任意一个点j,且点j没有和所有的点相连。
显然这个点只能为a或c,因为它和某个点之间没有边。【规则1】
那么我们就让这个点j设置为a;
①然后对于和j相连的所有点k,且点k不为b(即k不与其他所有点相连),那么点k
只能为a或c(因为k和某个点之间没有边)【规则1】
而根据【规则2】可知点k只能为a
②对于和j不相连的所有点k,显然k只能为c
根据①和②
会发现所有的点都已经染上色了
而点j为a或c其实不影响答案。
所以再O(n^2)根据规则判断一下这个染色是否可行就好了。
【代码】
#include <bits/stdc++.h>
using namespace std;
const int N = 500+10;
int c[N],n,m,chu[N+10];
bool b[N][N];
int main()
{
ios::sync_with_stdio(0),cin.tie(0);
#ifdef LOCAL_DEFINE
freopen("rush.txt","r",stdin);
#endif
cin >> n >> m;
for (int i = 1;i <= m;i++){
int x,y;
cin >> x >> y;
b[x][y] = b[y][x] = true;
chu[x]++;chu[y]++;
}
for (int i = 1;i <= n;i++)
if (chu[i]==(n-1))
c[i] = 2;
for (int i = 1;i <= n;i++)
if (c[i]!=2){
c[i] = 1;
for (int j = 1;j <= n;j++)
if (b[i][j] && c[j]!=2){
c[j] = 1;
}else if (i!=j && !b[i][j]){
c[j] = 3;
}
break;
}
for (int i = 1;i <= n;i++)
for (int j = 1;j <= n;j++)
if (b[i][j]){
if (abs(c[i]-c[j])>1) return cout<<"No"<<endl,0;
}else if (i!=j){
if (abs(c[i]-c[j])<=1) return cout<<"No"<<endl,0;
}
cout<<"Yes"<<endl;
for (int i = 1;i <= n;i++){
if (c[i]==1) cout<<'a';
if (c[i]==2) cout<<'b';
if (c[i]==3) cout<<'c';
}
return 0;
}
相关文章
- long转string mybatis_Long转String总结
- ORA-00295: datafile/tempfile number string is invalid, must be between 1 and string ORACLE 报错 故障修复 远程处理
- ORA-01235: END BACKUP failed for string file(s) and succeeded for string ORACLE 报错 故障修复 远程处理
- ORA-24279: view string is not a parallel access view ORACLE 报错 故障修复 远程处理
- ORA-25302: Operation not possible for non-buffered queue string ORACLE 报错 故障修复 远程处理
- ORA-26881: ORA-string: string raised in string automatic string job:”string”.”string” for Capture process “string” and cloned Capture process “string”. ORACLE 报错 故障修复 远程处理
- ORA-27424: calendar clauses string and string are incompatible ORACLE 报错 故障修复 远程处理
- ORA-28006: conflicting values for parameters string and string ORACLE 报错 故障修复 远程处理
- ORA-28110: policy function or package string.string has error ORACLE 报错 故障修复 远程处理
- ORA-29363: plan directive string, string is mandatory and cannot be modified or deleted ORACLE 报错 故障修复 远程处理
- ORA-30071: conversion between datetime/interval and string fail ORACLE 报错 故障修复 远程处理
- ORA-39030: invalid file type string ORACLE 报错 故障修复 远程处理
- ORA-47028: error deleting Factor Link for string and string, string ORACLE 报错 故障修复 远程处理
- ORA-47140: Factor expression string already defined ORACLE 报错 故障修复 远程处理
- ORA-56702: consumer group string is for internal use only and cannot be a switch target ORACLE 报错 故障修复 远程处理
- ORA-00093: string must be between string and string ORACLE 报错 故障修复 远程处理
- ORA-01378: The logical block size (string) of file string is not compatible with the disk sector size (media sector size is string and host sector size is string) ORACLE 报错 故障修复 远程处理
- ORA-01593: rollback segment optimal size (string blks) is smaller than the computed initial size (string blks) ORACLE 报错 故障修复 远程处理
- ORA-13390: error in spatial analysis and mining function: [string] ORACLE 报错 故障修复 远程处理
- ORA-15181: symbol [string] not found in library string, error [string] ORACLE 报错 故障修复 远程处理
- java.lang.String (JDK1.8)详解编程语言
- MySQL中AND的使用方法解析(mysql中and的用法)
- MySQL中的AND和OR使用逻辑运算符优化查询语句(mysql中and与or)