内容:染色划分,带权并查集,扩展并查集
Arpa’s overnight party and Mehrdad’s silent entering
题目链接
题目大意
- 个点围成一圈,分为对,对内两点不同染色
- 同时,相邻3个点之间必须有两个点不同染色
- 问构造出一种染色方案
解题思路
- 将每对进行的连边看作一类边
- 将为满足相邻3个点必须有两个点不同染色的边,看作二类边
- 满足构造方案,即将个点形成一个二分图,无奇环
- 对于只有一类边,形不成环,端点不同
- 对于二类边与一类边组合才能形成环
- 将二类边定义为
- 成环的情况只能,如下图
- 由于一类边不可能相连,中间必然是二类边,一类边交换,所以环上的点数为二类边的总点数,一定为偶数,只能形成偶环,构造成立
- 利用带权并查集实现
import java.io.*;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.BitSet;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;
import java.util.Vector;
public class Main{
static int find(int x,int[] fa,int[] relation) {
if(x==fa[x])return x;
else {
int f=fa[x];
fa[x]=find(fa[x], fa, relation);
relation[x]=(relation[x]+relation[f])%2;
return fa[x];
}
}
public static void main(String[] args) throws IOException{
AReader input=new AReader();
PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
int n=input.nextInt();
int[] fa=new int[2*n+1];
int[] relation=new int[2*n+1];
for(int i=1;i
食物链
题目链接
题目大意
- 个点,对关系
- 每个点可能为类,它们之间满足吃,吃,吃
- 对关系中,表示同类,表示吃
- 依次处理对关系,若当前关系与之前的关系矛盾,则视为错误
- (自己吃自己),均视为错误
- 问有多少对错误
解题思路
- 对个点进行种颜色的染色划分
- 类似黑白染色
- 利用带权并查集或扩展并查集实现
- 详见图论笔记
扩展并查集
import java.io.*;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.BitSet;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;
import java.util.Vector;
public class Main{
static int find(int x,int[] fa) {
if(x==fa[x])return x;
else return fa[x]=find(fa[x], fa);
}
public static void main(String[] args) throws IOException{
AReader input=new AReader();
PrintWriter out = new PrintWriter(new OutputSt服务器托管网reamWriter(System.out));
int n=input.nextInt();
int k=input.nextInt();
int[] fa=new int[3*n+1];
for(int i=1;in||y>n) {
ans++;
continue;
}
if(op==1) {
if(find(x, fa)==find(y+n, fa)||find(y, fa)==find(x+n, fa)) {
//x吃y或y吃x
//x吃y=>xA->yB,xB->yC,xC->yA
//y吃x=>yA->xB,yB->xC->yC->xA
ans++;
continue;
}
fa[find(x, fa)]=find(y, fa);
fa[find(x+n,服务器托管网 fa)]=find(y+n, fa);
fa[find(x+2*n, fa)]=find(y+2*n, fa);
}else {
if(x==y) {
ans++;
continue;
}
if(find(x, fa)==find(y, fa)||find(y, fa)==find(x+n, fa)) {
//x和y是同类,y吃x
ans++;
continue;
}
fa[find(x, fa)]=find(y+n, fa);
fa[find(x+n, fa)]=find(y+2*n, fa);
fa[find(x+2*n, fa)]=find(y, fa);
}
}
out.print(ans);
out.flush();
out.close();
}
static
class AReader{
BufferedReader bf;
StringTokenizer st;
BufferedWriter bw;
public AReader(){
bf=new BufferedReader(new InputStreamReader(System.in));
st=new StringTokenizer("");
bw=new BufferedWriter(new OutputStreamWriter(System.out));
}
public String nextLine() throws IOException{
return bf.readLine();
}
public String next() throws IOException{
while(!st.hasMoreTokens()){
st=new StringTokenizer(bf.readLine());
}
return st.nextToken();
}
public char nextChar() throws IOException{
//确定下一个token只有一个字符的时候再用
return next().charAt(0);
}
public int nextInt() throws IOException{
return Integer.parseInt(next());
}
public long nextLong() throws IOException{
return Long.parseLong(next());
}
public double nextDouble() throws IOException{
return Double.parseDouble(next());
}
public float nextFloat() throws IOException{
return Float.parseFloat(next());
}
public byte nextByte() throws IOException{
return Byte.parseByte(next());
}
public short nextShort() throws IOException{
return Short.parseShort(next());
}
public BigInteger nextBigInteger() throws IOException{
return new BigInteger(next());
}
public void println() throws IOException {
bw.newLine();
}
public void println(int[] arr) throws IOException{
for (int value : arr) {
bw.write(value + " ");
}
println();
}
public void println(int l, int r, int[] arr) throws IOException{
for (int i = l; i
带权并查集
import java.io.*;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.BitSet;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;
import java.util.Vector;
public class Main{
static int find(int x,int[] fa,int[] relation) {
if(x==fa[x])return x;
else {
int f=fa[x];
fa[x]=find(fa[x], fa, relation);
relation[x]=(relation[x]+relation[f])%3;
return fa[x];
}
}
public static void main(String[] args) throws IOException{
AReader input=new AReader();
PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
int n=input.nextInt();
int k=input.nextInt();
int ans=0;
int[] fa=new int[n+1];
int[] relation=new int[n+1];
for(int i=1;in||y>n) {
ans++;
continue;
}
if(op==1) {
int fx=find(x, fa, relation);
int fy=find(y, fa, relation);
if(fx==fy) {
if(relation[x]!=relation[y]) {
ans++;
continue;
}
}else {
fa[fx]=fy;
relation[fx]=(relation[y]+0-relation[x]+3)%3;
}
}else {
if(x==y) {
ans++;
continue;
}
int fx=find(x, fa, relation);
int fy=find(y, fa, relation);
if(fx==fy) {//0吃1,1吃2,2吃0
if(relation[x]==0&&relation[y]==1||
relation[x]==1&&relation[y]==2||
relation[x]==2&&relation[y]==0)continue;
ans++;
continue;
}else {
fa[fx]=fy;
relation[fx]=(relation[y]+2-relation[x]+3)%3;
}
}
}
out.println(ans);
out.flush();
out.close();
}
static
class AReader{
BufferedReader bf;
StringTokenizer st;
BufferedWriter bw;
public AReader(){
bf=new BufferedReader(new InputStreamReader(System.in));
st=new StringTokenizer("");
bw=new BufferedWriter(new OutputStreamWriter(System.out));
}
public String nextLine() throws IOException{
return bf.readLine();
}
public String next() throws IOException{
while(!st.hasMoreTokens()){
st=new StringTokenizer(bf.readLine());
}
return st.nextToken();
}
public char nextChar() throws IOException{
//确定下一个token只有一个字符的时候再用
return next().charAt(0);
}
public int nextInt() throws IOException{
return Integer.parseInt(next());
}
public long nextLong() throws IOException{
return Long.parseLong(next());
}
public double nextDouble() throws IOException{
return Double.parseDouble(next());
}
public float nextFloat() throws IOException{
return Float.parseFloat(next());
}
public byte nextByte() throws IOException{
return Byte.parseByte(next());
}
public short nextShort() throws IOException{
return Short.parseShort(next());
}
public BigInteger nextBigInteger() throws IOException{
return new BigInteger(next());
}
public void println() throws IOException {
bw.newLine();
}
public void println(int[] arr) throws IOException{
for (int value : arr) {
bw.write(value + " ");
}
println();
}
public void println(int l, int r, int[] arr) throws IOException{
for (int i = l; i
服务器托管,北京服务器托管,服务器租用 http://www.fwqtg.net
相关推荐: uniapp H5 touchstart执行完成并返回成功再执行touchend 失败则不执行touchend
uniapp H5 touchstart执行完成并返回成功再执行touchend 失败则不执行touchend 直接上代码 tmmplate> // 只绑定 touchstart 事件 view class=”mp_yun_item”> view …