一句话题意

以图论方式给出一个电路，判断此电路的特征

题解

思路

并联，串联的判断

首先，根据 T Y J TYJ TYJ老师的讲解，我们可以知道在一个电路中，若电源与一个用电器之间只有导线，则可以看做用电器与电源直接相连，如下图：

在这张图中 L 1 L1 L1， L 2 L2 L2由于和电源的正极只用导线相连，所以可以视为 L 1 L1 L1， L 2 L2 L2的左端就是 + + +极， L 3 L3 L3的右端就是 − – −极

OK，当我们明白了这一点后，我们再引入几个定理

1. 假设这个电路无短路情况，首先对电路进行上述变形
2. 若这个电路中所有用电器两端都直接连接正负极，则这个电路一定是并联的

1. 反之，若一个电路图中，恰好有一对用电器，一个只连接正极，一个只连接负极，那么就是串联
   
2. 若以上两种情况都存在，则是混联

短路的判断

1.局部短路

像这张图， L 1 L1 L1会出现局部短路，那么怎么判断呢？如果使用我们上面的方法，我们走出来是这样的：

我们发现， L 1 L1 L1的两端都是 + + +极啦，所以我们可以发现，只要做了上述操作后，若有一个用电器两端都是 + + +极，那么就有局部短路的存在

2. 电源短路

这，是一个会电源短路的电路，我们还是按照上面的做法：

我们发现，当我们对 + + +极操作后，电源的负极直接连上了正极，这是就是电源短路了，注意，这时在上面的判断方法下，用电器也短路了，所以实现的时候记得注意优先极哈。。。

实现：

配合着代码理解一下吧：

#include<cstdio>
#include<iostream>
#include<vector>
#include<map>
using namespace std;
const int MAXN=105;
char type[MAXN];
int flag[MAXN];
vector<int> g[MAXN];
map<char,int> pre;
void add(int u,int v,char x,char y){ 
	u=u*2+pre[x];
	v=v*2+pre[y];
	g[u].push_back(v);
	g[v].push_back(u);
}
void dfs(int u,int fa,int t){ 
	flag[u]=t;
	for(int j=0;j<g[u].size();j++){ 
		int v=g[u][j];
		if(v!=fa){ 
			dfs(v,u,t);
		}
	}
}
void pre_map(){ 
	pre['L']=0;
	pre['R']=1;
	pre['E']=0;
}
int main(){ 
	pre_map();
	int n,m;
	scanf("%d %d",&n,&m);
	int q;
	for(int i=1;i<=n;i++){ 
		char s[5];
		scanf("%s",s);
		type[i]=s[0];
		if(s[0]=='Q'){ 
			q=i;
		}
		if(s[0]=='F'){ 
			add(i,i,'L','R');
		}
	}
	for(int i=1;i<=m;i++){ 
		int u,v;
		char x,y;
		scanf("%d %d %c %c",&u,&v,&x,&y);
		add(u,v,x,y);
		add(v,u,y,x);
	}
	dfs(q*2,-1,1);
	if(flag[q*2+1]==1){ 
		printf("BOOM!");
		return 0;
	}
	for(int i=1;i<=n;i++){ 
		if(type[i]=='M'){ 
			if(flag[i*2]==flag[i*2+1] && (flag[i*2]!=0 || flag[i*2+1]!=0)){ 
				printf("It's not bright enough");
				return 0;
			}
		}
	}
	dfs(q*2+1,-1,-1);
// for(int i=1;i<=n;i++){ 
// printf("%d:%d %d\n",i,flag[i*2],flag[i*2+1]);
// } 
	bool QAQ=false;
	bool f3=true;
	int f2=0,f5=0;
	for(int i=1;i<=n;i++){ 
		if(type[i]=='M'){ 
// cerr<<flag[i*2]<<" "<<flag[i*2+1]<<endl;
			if(flag[i*2]+flag[i*2+1]!=0){ 
				f3=false;
			}
			if(flag[i*2]+flag[i*2+1]==0){ 
				QAQ=true;
			}
			if(flag[i*2]==-1 && flag[i*2+1]==0){ 
				f2++;
			}
			if(flag[i*2]==1 && flag[i*2+1]==0){ 
				f5++;
			}
			if(flag[i*2]==0 && flag[i*2+1]==-1){ 
				f2++;
			}
			if(flag[i*2]==0 && flag[i*2+1]==1){ 
				f5++;
			}
		}
	}
	if(f3==true && QAQ==true){ 
		printf("Separate lights");
	}
	else if(f2==1 && f5==1 && QAQ==false){ 
		printf("Light up together");
	}
	else{ 
		printf("Ethereal light!");
	}
return 0;
}