分析:
明显的二分答案,但是写判断函数时一定要用二分图染色,我一开始想的是用vis[]数组表示,vis[i]==0时说明i犯人待分配,vis[i]==1说明i犯人分配到集合1,vis[i]==2说明i犯人分配到集合2,然后搞好几个判断,但是这样错误很明显,假设 ①与②分别分到监狱一和二,④和③分别分到监狱一和二,这时如果②和③不能分到一起,判断就会return false,但是其实可以①③一起,②④一起。。。
下面这个是错的:
//错的错的错的 才20分 1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 using namespace std; 8 typedef long long LL; 9 LL N,M;10 struct node{11 LL a,b,c;12 };13 node pris[1000000];14 LL cmp(const node &q,const node &w){15 if(q.c >1;40 if(jud(mid)==true){41 find(l,mid);42 }43 else{44 find(mid+1,r);45 }46 }47 bool jud(LL x){48 LL vis[200000];49 memset(vis,0,sizeof(vis));50 for(LL i=1;i<=M;i++){51 LL u=pris[i].a;52 LL v=pris[i].b;53 if(pris[i].c>x){ //可能会有冲突 54 if(vis[u]==0&&vis[v]==0){ //没有确定集合 55 vis[u]=1;56 vis[v]=2;57 }58 else{59 if(vis[u]!=0&&vis[v]!=0&&vis[u]==vis[v]) return false;//必然爆发冲突 60 else{61 if(vis[u]!=0&&vis[v]==0){62 if(vis[u]==1) vis[v]=2;63 else if(vis[u]==2) vis[v]=1;64 }65 else if(vis[u]==0&&vis[v]!=0){66 if(vis[v]==1) vis[u]=2;67 else if(vis[v]==2) vis[u]=1;68 }69 } 70 }71 }72 }73 74 return true;75 }
正解是二分图染色,由于有20000个点,所以应该用vector,不过因为图不是太稠密,所以开to[20001][500]也能过。
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 using namespace std;10 typedef long long LL;11 LL N,M;12 struct node{13 LL a,b,c;14 };15 node pris[100005];16 LL cmp(const node &q,const node &w){17 if(q.c >1;45 if(jud(mid)==true){46 find(l,mid);47 }48 else{49 find(mid+1,r);50 }51 }52 bool jud(LL x){53 memset(vis,0,sizeof(vis));54 memset(to,0,sizeof(to));55 for(LL i=1;i<=M;i++){56 LL u=pris[i].a;57 LL v=pris[i].b;58 if(pris[i].c>x){59 to[u][0]++;60 to[v][0]++;61 to[u][to[u][0]]=v;62 to[v][to[v][0]]=u;63 }64 }65 for(LL i=1;i<=N;i++){66 if(vis[i]==0&&to[i][0]>0){67 if(color(i)==false) return false;68 }69 }70 return true;71 }72 bool color(LL root){73 vis[root]=1;74 static queue Q;75 while(Q.size()>0) Q.pop();76 Q.push(root);77 while(Q.size()>0){78 int x=Q.front();79 Q.pop();80 for(int i=1;i<=to[x][0];i++){81 int y=to[x][i];82 if(vis[y]==0){83 if(vis[x]==1) vis[y]=2;84 else vis[y]=1;85 Q.push(y);86 }87 else if(vis[y]==vis[x]) return false;88 }89 }90 return true;91 }