|
|
back to boardAnd in this one, what's wrong??? Posted by ijk 23 Mar 2002 05:44 #include<iostream.h> #include<stdlib.h> #define NONE -1 #define ONE 0 #define TWO 1 class Queue { private: short last,first; short q[100]; public: Queue(){first=last=-1;} void push(short a) { last=(last+1)%100; q[last]=a; } short pop() { first=(first+1)%100; return q[first]; } char empty(){return (first==last);} }; short N; char notknow[100][100]; short team[100]; short reach[100]; short in1, in2; short one[100]; void color(short i, short COL) { short j, k; Queue queue; reach[i]++; team[i]=COL; if (team[i]==ONE) one[i]++; queue.push(i); while (!queue.empty()) { j = queue.pop(); for (k=0; k<N; k++) if (notknow[j][k]==1) { if (team[k]==NONE) { reach[i]++; team[k]=(team[j]+1)%2; if (team[k]==ONE) one[i]++; queue.push(k); continue; } if (team[k]==team[j]) { cout<<"No solution"; exit(0); } } } } void main() { short i, j, pos; cin>>N; for (i=0; i<N; i++) for (j=0; j<N; j++) notknow[i][j]=1; for (i=0; i<N; i++) notknow[i][i]=0; for (i=0; i<N; i++) { cin>>j; while (j>0) { notknow[i][j-1]=0; cin>>j; } } for (i=0; i<N; i++) for (j=0; j<N; j++) if (notknow[i][j]==1) notknow[j][i]= 1; for (i=0; i<N; i++) { reach[i]=0; one[i]=0; team[i]=NONE; } for (i=0; i<N; i++) if (team[i]==NONE) color(i,ONE); int name[100], h; for (i=0; i<N; i++) name[i]=i; for (i=0; i<N-1; i++) { pos=i; for (j=i+1; j<N; j++) if (one[j]>one[pos])pos=j; if (pos!=i) { h=name[i], name[i]=name[pos], name[pos]=h; h=reach[i],reach[i]=reach[pos],reach[pos]=h; h=one[i], one[i]=one[pos], one[pos]=h; } } in1 = 0; in2 = 0; for (i=0; i<N; i++) team[i]=NONE; for (i=0; i<N; i++) if (team[name[i]]==NONE) { if (in1>in2) { if (one[i]>=reach[i]-one[i]) { in2+=one[i]; in1+=(reach[i]-one[i]); color(name[i],TWO); } else { in2+=(reach[i]-one[i]); in1+=one[i]; color(name[i],ONE); } } else { if (one[i]>=reach[i]-one[i]) { in1+=one[i]; in2+=(reach[i]-one[i]); color(name[i],ONE); } else { in1+=(reach[i]-one[i]); in2+=one[i]; color(name[i],TWO); } } } cout<<in1<<" "; for (i=0; i<N; i++) if (team[i]==ONE) cout<<(i+1)<<" "; cout<<endl; cout<<in2<<" "; for (i=0; i<N; i++) if (team[i]==TWO) cout<<(i+1)<<" "; } |
|
|