[BFS]JZOJ 4672 Graph Coloring

Description

現在你有一張無向圖包含n個節點m條邊。最初，每一條邊都是藍色或者紅色。每一次你可以將一個節點連接的所有邊變色（從紅變藍，藍變紅）。
找到一種步數最小的方案，使得所有邊的顏色相同。

Input

第一行包含兩個數n,m（1<=n,m<=100000）分別代表節點數和邊的數量
接下來m行描述邊，第i行ui,vi,ci，代表ui有一條顏色為ci的邊與vi相連（ci是B或者是R），B代表藍色，R代表紅色。數據保證沒有自環的邊。

Output

如果沒有方案就輸出-1。否則第一行輸出k代表最小的步數

Sample Input

輸入1：
3 3
1 2 B
3 1 R
3 2 B輸入3：
4 5
1 2 R
1 3 R
2 3 B
3 4 B
1 4 B

Sample Output

輸出1：
1輸出3：
-1

Data Constraint

對于30%數據，n<=20,m<=20

分析

非常簡單的染色問題

我們分兩次BFS，一次選擇把全部邊變成紅色，另一次顯然

然后一個點顯然變兩次是一樣的，所以我們當邊的顏色是否與當前選擇的顏色不同給連接的點染色，若已染則判斷是否相同或不同

?

#include <iostream>
#include <cstdio>
#include <queue>
#include <memory.h>
using namespace std;
const int N=1e5+10;;
struct Edge {int u,v,nx,type;
}g[2*N];
int cnt,list[N];
int n,m; 
bool b[N],vis[N];
int ok,ans=2147483647,lans[2];void Add(int u,int v,char type) {g[++cnt]=(Edge){u,v,list[u],type=='R'?1:0};list[u]=cnt;g[++cnt]=(Edge){v,u,list[v],type=='R'?1:0};list[v]=cnt;
}int BFS(int v0,int same) {queue<int> q;while (!q.empty()) q.pop();q.push(v0);vis[v0]=1;lans[1]++;while (!q.empty()) {int u=q.front();q.pop();for (int i=list[u];i;i=g[i].nx) {if (!vis[g[i].v]) {b[g[i].v]=g[i].type==same?b[u]:(b[u]^1);lans[b[u]^(g[i].type==same)]++;q.push(g[i].v);vis[g[i].v]=1;}elseif (g[i].type==same&&b[u]!=b[g[i].v]||g[i].type!=same&&b[u]==b[g[i].v]) return -1;}}return min(lans[0],lans[1]);
}int main() {scanf("%d%d",&n,&m);for (int i=1;i<=m;i++) {int u,v;char c;scanf("%d%d",&u,&v);scanf("%c",&c);while (c!='R'&&c!='B') scanf("%c",&c);Add(u,v,c);}for (int i=0;i<2;i++) {bool p=1;int cans=0,nans=0;memset(b,0,sizeof b);memset(vis,0,sizeof vis);for (int j=1;j<=n;j++) if (!vis[j]) {lans[0]=lans[1]=0;cans=BFS(j,i);if (cans==-1) {p=0;break;}nans+=cans;}if (p) ans=min(ans,nans);ok+=p;}if (!ok) printf("-1");else printf("%d",ans);
}

?