房产门户网站建设,网站建设仿站企业公司,成都seo网络优化公司,网站logo怎么设置Description 现在你有一张无向图包含n个节点m条边。最初#xff0c;每一条边都是蓝色或者红色。每一次你可以将一个节点连接的所有边变色#xff08;从红变蓝#xff0c;蓝变红#xff09;。找到一种步数最小的方案#xff0c;使得所有边的颜色相同。Input 第一行包含两个…Description 现在你有一张无向图包含n个节点m条边。最初每一条边都是蓝色或者红色。每一次你可以将一个节点连接的所有边变色从红变蓝蓝变红。找到一种步数最小的方案使得所有边的颜色相同。 Input 第一行包含两个数n,m1n,m100000分别代表节点数和边的数量接下来m行描述边第i行ui,vi,ci代表ui有一条颜色为ci的边与vi相连ci是B或者是RB代表蓝色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%数据n20,m20 分析 非常简单的染色问题 我们分两次BFS一次选择把全部边变成红色另一次显然 然后一个点显然变两次是一样的所以我们当边的颜色是否与当前选择的颜色不同给连接的点染色若已染则判断是否相同或不同 #include iostream
#include cstdio
#include queue
#include memory.h
using namespace std;
const int N1e510;;
struct Edge {int u,v,nx,type;
}g[2*N];
int cnt,list[N];
int n,m;
bool b[N],vis[N];
int ok,ans2147483647,lans[2];void Add(int u,int v,char type) {g[cnt](Edge){u,v,list[u],typeR?1:0};list[u]cnt;g[cnt](Edge){v,u,list[v],typeR?1:0};list[v]cnt;
}int BFS(int v0,int same) {queueint q;while (!q.empty()) q.pop();q.push(v0);vis[v0]1;lans[1];while (!q.empty()) {int uq.front();q.pop();for (int ilist[u];i;ig[i].nx) {if (!vis[g[i].v]) {b[g[i].v]g[i].typesame?b[u]:(b[u]^1);lans[b[u]^(g[i].typesame)];q.push(g[i].v);vis[g[i].v]1;}elseif (g[i].typesameb[u]!b[g[i].v]||g[i].type!sameb[u]b[g[i].v]) return -1;}}return min(lans[0],lans[1]);
}int main() {scanf(%d%d,n,m);for (int i1;im;i) {int u,v;char c;scanf(%d%d,u,v);scanf(%c,c);while (c!Rc!B) scanf(%c,c);Add(u,v,c);}for (int i0;i2;i) {bool p1;int cans0,nans0;memset(b,0,sizeof b);memset(vis,0,sizeof vis);for (int j1;jn;j) if (!vis[j]) {lans[0]lans[1]0;cansBFS(j,i);if (cans-1) {p0;break;}nanscans;}if (p) ansmin(ans,nans);okp;}if (!ok) printf(-1);else printf(%d,ans);
} View Code 转载于:https://www.cnblogs.com/mastervan/p/10764860.html
