一句話題意

以圖論方式給出一個電路，判斷此電路的特征

題解

思路

并聯，串聯的判斷

首先，根據 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，當我們明白了這一點后，我們再引入幾個定理

0. 假設這個電路無短路情況，首先對電路進行上述變形
1. 若這個電路中所有用電器兩端都直接連接正負極，則這個電路一定是并聯的

2. 反之，若一個電路圖中，恰好有一對用電器，一個只連接正極，一個只連接負極，那么就是串聯
   
3. 若以上兩種情況都存在，則是并聯

短路的判斷

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;
}