题意:有n(1<=n<=100)个点的无向图,每条路的值是0或者1,King要把所有的边染色成1,但是修路的人很二逼,King让他去搞 i 点的时候
他不仅把与 i 点相连的0变成1同时也把1变成0,问能不能找到一种方法使得所有0都变成1,spj。
题解:1 可以清楚的意识到一个点至多搞一次,枚举第一个点的状态然后同一个连通块的点的状态就可以定下来,dfs判定可行性即可。 但是图可能是不连通的唉。
2 并查集,维护当前集合中根节点不取的时候其他节点与根节点的关系即可。
Sure原创,转载请注明出处。
dfs:
#include <iostream> #include <cstdio> #include <memory.h> #include <algorithm> using namespace std; const int maxn = 102; const int maxe = 10002; struct node { int v,c; int next; }edge[maxe]; int head[maxn],ans[maxn],vis[maxn]; bool record[maxn]; int m,n,idx,top; void init() { memset(head,-1,sizeof(head)); memset(record,false,sizeof(record)); idx = top = 0; return; } void addedge(int u,int v,int c) { edge[idx].v = v; edge[idx].c = c; edge[idx].next = head[u]; head[u] = idx++; edge[idx].v = u; edge[idx].c = c; edge[idx].next = head[v]; head[v] = idx++; return; } void read() { int u,v,w; for(int i=0;i<m;i++) { scanf("%d %d %d",&u,&v,&w); addedge(u,v,w); } return; } bool dfs(int st,int val) { vis[st] = val; if(val == 1) { ans[top++] = st; } bool flag = true; for(int i=head[st];i != -1;i=edge[i].next) { if(vis[edge[i].v] == -1) { if(dfs(edge[i].v , 1 ^ (edge[i].c ^ val)) == false) { flag = false; break; } } else { int tmp = (val + vis[edge[i].v]) % 2; if(tmp == edge[i].c) { flag = false; break; } } } return flag; } void out() { printf("%d\n",top); for(int i=0;i<top;i++) { if(i) printf(" "); printf("%d",ans[i]); } puts(""); return; } void solve() { bool flag = true; top = 0; for(int i=1;i<=n;i++) { int bj = top; if(record[i] == false) { memset(vis,-1,sizeof(vis)); if(dfs(i , 0)) { for(int j=1;j<=n;j++) { if(vis[j] != -1) { record[j] = true; } } } else { memset(vis,-1,sizeof(vis)); top = bj; if(dfs(i , 1)) { for(int j=1;j<=n;j++) { if(vis[j] != -1) { record[j] = true; } } } else { flag = false; break; } } } } if(flag == false) puts("Impossible"); else out(); return; } int main() { while(~scanf("%d %d",&n,&m)) { init(); read(); solve(); } return 0; }
并查集:
#include <iostream> #include <cstdio> #include <memory.h> using namespace std; const int maxn = 102; int father[maxn],dis[maxn],ans[maxn]; int m,n; int find(int u) { if(u == father[u]) return father[u]; int t = father[u]; father[u] = find(father[u]); dis[u] ^= dis[t]; return father[u]; } void init() { for(int i=1;i<=n;i++) { father[i] = i; dis[i] = 0; } return; } void solve() { int u,v,c; bool flag = true; while(m--) { scanf("%d %d %d",&u,&v,&c); if(flag == false) continue; int x = find(u); int y = find(v); if(x == y) { if((dis[u] ^ dis[v] ^ c) == 0) { flag = false; } } else { father[y] = x; dis[y] = 1 ^ dis[u] ^ dis[v] ^ c; } } if(flag == false) puts("Impossible"); else { int top = 0; for(int i=1;i<=n;i++) { find(i); if(dis[i]) ans[top++] = i; } printf("%d\n",top); for(int i=0;i<top;i++) { if(i) printf(" "); printf("%d",ans[i]); } puts(""); } return; } int main() { while(~scanf("%d %d",&n,&m)) { init(); solve(); } return 0; }