CSU 1574 Amanda Lounges 模拟题

#include<iostream> #include<stdio.h> #include<string.h> #include<queue> #include<math.h> #include<vector> using namespace std; template <class T> inline bool rd(T &ret) { char c; int sgn; if(c=getchar(),c==EOF) return 0; while(c!='-'&&(c<'0'||c>'9')) c=getchar(); sgn=(c=='-')?⑴:1; ret=(c=='-')?0:(c-'0'); while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0'); ret*=sgn; return 1; } template <class T> inline void pt(T x) { if (x <0) { putchar('-'); x = -x; } if(x>9) pt(x/10); putchar(x%10+'0'); } const int N = 200105; const int M = N<<1; typedef pair<int,int> pii; vector<pii>G; struct Edge{ int from,to,col,nex; }edge[M]; //注意 N M 要修改 int head[N],edgenum; void add(int u,int v,int col){ Edge E = {u,v,head[u]}; edge[edgenum] = E; head[u] = edgenum ++; } void init(){ memset(head,⑴,sizeof head); edgenum = 0; } int c[N],ans,n,m; int bfs(int x){ int siz = 1,ran = 1; c[x] = 1; queue<int>q; q.push(x); // printf("bfs:%d's color = %d ",x,c[x]); while(!q.empty()){ int u = q.front(); q.pop(); for(int i = head[u]; ~i; i = edge[i].nex){ int v = edge[i].to; // printf("bfs_edge(%d,%d)-(%d,%d) ",u,c[u],c[v]); if(c[v]!=⑴){ // printf("sum = %d ",c[u]+c[v]); if((c[u]+c[v])!=1)return ⑴; } else { siz++; c[v] = c[u]^1; ran += c[v]; q.push(v); // printf("%d's color = %d ",c[v]); } } } return min(ran,siz-ran); } bool solve(){ int u,d; memset(c,sizeof c); for(int i = 0; i < m; i++){ rd(u); rd(v); rd(d); add(u,d); add(v,d); } queue<int>q; for(int i = 0; i < edgenum; i+=2){ u = edge[i].from; v = edge[i].to; d = edge[i].col; if(d == 0){ if(c[u]==1 || c[v] == 1)return false; if(c[u]==⑴)q.push(u),c[u] = 0; if(c[v]==⑴)q.push(v),c[v] = 0; } else if(d == 2){ if(c[u] == 0 || c[v] == 0)return false; if(c[u]==⑴)q.push(u),c[u] = 1; if(c[v]==⑴)q.push(v),c[v] = 1; } } while(!q.empty()){ u = q.front(); q.pop(); for(int i = head[u];~i;i=edge[i].nex){ v = edge[i].to; if(c[v]!=⑴){ if(edge[i].col != c[u]+c[v])return false; } else { c[v] = c[u]^1; q.push(v); } } } // puts("init:"); for(int i = 1; i <= n; i++)printf("(%d'color is %d) ",i,c[i]); for(int i = 1; i <= n; i++)ans += c[i] == 1; G.clear(); for(int i = 0; i < edgenum; i+=2){ if(edge[i].col != 1)continue; u = edge[i].from; v = edge[i].to; if(c[u]==⑴ && c[v]==⑴)G.push_back(pii(u,v)); } init(); for(int i = 0; i < (int)G.size(); i++){ u = G[i].first; v = G[i].second; add(u,1); add(v,1); // printf("addedge (%d,v); } for(int i = 1; i <= n; i++) if(c[i] == ⑴){ int tmp = bfs(i); if(tmp == ⑴)return false; ans += tmp; } return true; } int main(){ while(~scanf("%d %d",&n,&m)){ init(); ans = 0; if(false == solve())puts("impossible"); else cout<<ans<<endl; } return 0; } /* 5 4 1 2 2 2 3 1 3 4 1 4 5 1 ans:3 5 5 1 2 2 2 3 1 3 4 1 4 5 1 3 5 1 ans:im 5 6 1 2 2 2 3 1 3 4 1 4 5 1 3 6 0 5 6 0 ans:3 9 8 1 2 2 2 3 1 3 4 1 4 5 1 3 6 0 5 6 0 7 8 1 8 9 1 ans:4 9 9 1 2 2 2 3 1 3 4 1 4 5 1 3 6 0 5 6 0 7 8 1 8 9 1 9 7 1 ans:im */