正題

---

題目大意

一張無向圖，每條邊有一個顏色(紅或藍)，可以選擇點使得連接的邊都取反，求至少要選多個點可以使得所有邊的顏色相同。

---

解題思路

不難發現如果確定所有邊的顏色，然后知道一個點的選擇后就可以知道整個聯通圖的選擇。因為如果一個點的選擇被確定了，他連接的點的選擇也可以被確定。

---

$code$

#include<cstdio> #include<algorithm> #include<cstring> using namespace std; const int N=110000,inf=2147483647/3; struct edge{int to,next,w; }a[N*2]; int ls[N],tot,mins,sum,n,m; bool v[N],f[N],flag,run[N]; void addl(int x,int y,char w) {a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot;a[tot].w=(w=='R'); } void dfs(int x) {v[x]=run[x]=1;for(int i=ls[x];i;i=a[i].next){if(flag) break;int y=a[i].to;if(!v[y]){f[y]=f[x]^a[i].w;if(f[y]) sum++;dfs(y);}else if(f[y]!=f[x]^a[i].w)flag=1;} } void get_ans() {memset(run,0,sizeof(run));int ans=0,k;for(int i=1;i<=n;i++)if(!run[i]){f[i]=sum=flag=0;memset(v,0,sizeof(v));dfs(i);if(flag) k=inf;else k=sum;f[i]=sum=1;flag=0;memset(v,0,sizeof(v));dfs(i);if(flag) sum=inf;if(k==inf&&sum==inf){ans=inf;break;}ans+=min(k,sum);}mins=min(ans,mins); } int main() {scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){int x,y;char c;scanf("%d %d %c",&x,&y,&c);addl(x,y,c);addl(y,x,c);}mins=inf;get_ans();for(int i=1;i<=tot;i++)a[i].w^=1;get_ans();if(mins==inf) printf("-1");else printf("%d",mins); }

總結

以上是生活随笔為你收集整理的jzoj4672-Graph Coloring【图论,模拟】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。