題意：給出 n 個(gè)人，以及 m 對(duì)互不認(rèn)識(shí)的關(guān)系，剩余的人都互相認(rèn)識(shí)，要將所有人分成兩組，組內(nèi)不能有互不認(rèn)識(shí)的人，要求每組至少有一人，并且第一組人數(shù)盡量多，問(wèn)兩組人數(shù)或不可能時(shí)單獨(dú)輸出

BC 48 場(chǎng)的B題，這兩天黑白染色做的不少，要把互不認(rèn)識(shí)的人分在不同的組里，其實(shí)就是看整個(gè)圖是否能夠形成二分圖，如果不能形成二分圖的話，那么說(shuō)明圖中一定存在奇環(huán)，那么人就不能分在兩個(gè)組中而保證組內(nèi)都認(rèn)識(shí)。所以就是判二分圖，用黑白染色，然后將染色后數(shù)量多的點(diǎn)分在第一組，剩余分在第二組。但是題中有坑點(diǎn)，首先，人數(shù)小于等于1時(shí)，本來(lái)就分不成兩組來(lái)保證每組至少一人，所以需要特判，其次如果沒(méi)有人互不認(rèn)識(shí)，即所有區(qū)塊都是單點(diǎn)，那么就會(huì)出現(xiàn)所有人被分在第一組而第二組沒(méi)有人的情況，那么就要將一個(gè)人分到第二組去。

1 #pragma comment(linker,"/STACK:16777216") 2 #include<stdio.h> 3 #include<string.h> 4 5 typedef long long ll; 6 7 int head[100005],nxt[200005],point[200005],size=0; 8 bool f=0; 9 int num[2]; 10 int c[100005]; 11 12 void add(int a,int b){ 13 point[size]=b; 14 nxt[size]=head[a]; 15 head[a]=size++; 16 point[size]=a; 17 nxt[size]=head[b]; 18 head[b]=size++; 19 } 20 21 void dfs(int a,int x){ 22 if(f)return; 23 c[a]=x; 24 num[x]++; 25 for(int i=head[a];~i;i=nxt[i]){ 26 int b=point[i]; 27 if(c[b]==-1)dfs(b,!x); 28 else if(c[b]==x){ 29 f=1; 30 return; 31 } 32 } 33 } 34 35 int main(){ 36 int T; 37 scanf("%d",&T); 38 while(T--){ 39 memset(head,-1,sizeof(head)); 40 size=0; 41 f=0; 42 memset(c,-1,sizeof(c)); 43 int n,m; 44 scanf("%d%d",&n,&m); 45 int i; 46 for(i=1;i<=m;i++){ 47 int a,b; 48 scanf("%d%d",&a,&b); 49 add(a,b); 50 } 51 if(n<=1){ 52 printf("Poor wyh\n"); 53 continue; 54 } 55 int ans1=0,ans2=0; 56 for(i=1;i<=n&&(!f);i++){ 57 if(c[i]==-1){ 58 num[0]=num[1]=0; 59 dfs(i,1); 60 if(num[0]>num[1]){ 61 ans1+=num[0]; 62 ans2+=num[1]; 63 } 64 else{ 65 ans1+=num[1]; 66 ans2+=num[0]; 67 } 68 } 69 } 70 if(ans2==0){ans1--;ans2++;} 71 if(f)printf("Poor wyh\n"); 72 else printf("%d %d\n",ans1,ans2); 73 } 74 return 0; 75 } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/cenariusxz/p/4676940.html

《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的hdu 5285 二分图黑白染色的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。