今天下午的二分圖染色給我開啟新世界的大門啊2333333

這個題要比剛才的關押罪犯簡單，只需要染一遍色就能求出答案

#include<iostream> #include<cstring> #include<cstdio> #include<vector> #include<queue> using namespace std; int t,n,m,col[100005],x,y,ans; vector<int>mmp[100005]; queue<int>qwq; bool flag; inline void bfs(int x) {while(!qwq.empty())qwq.pop();qwq.push(x),col[x]=1;flag=0;//col[i]1為白，2為黑 int whi=1,bla=0;//計算有多少個黑白點 while(!qwq.empty()){int qaq=qwq.front();for(int i=0;i<mmp[qaq].size();i++){int to=mmp[qaq][i];if(col[to])//如果發現這個點之前到過 {if(col[to]==col[qaq])//如果這個點和隊首一樣 {flag=1;return;//答案不可行 }}else{col[to]=3-col[qaq];if(col[to]==1)whi++;elsebla++;qwq.push(to);}}qwq.pop();}ans+=max(whi,bla);//ans取黑白的最大值，因為假如黑的比白的多，我們把開始變為黑的就能得到白的比黑的多。黑白可以互相轉化 } int main() {scanf("%d",&t);while(t--){scanf("%d%d",&n,&m);flag=0,ans=0;for(int i=1;i<=n;i++)col[i]=0,mmp[i].clear();if(n==0)//連人都沒有就別管了23333 {printf("Poor wyh\n");continue;}for(int i=1;i<=m;i++)scanf("%d%d",&x,&y),mmp[x].push_back(y),mmp[y].push_back(x);for(int i=1;i<=n;i++)//如果發現這個點沒有被跑過，就進行bfs if(!col[i]){bfs(i);if(flag)//如果發現答案不可行直接退出 break;}if(flag) printf("Poor wyh\n");else{if(m==0){if(ans==1)//如果就一個人，無法滿足兩個集合 都有人的情況 printf("Poor wyh\n");else//沒有限制條件的情況下肯定能夠分到一遍只剩一個人 printf("%d %d\n",ans-1,1);}else//不為零肯定能分成ans n-ans printf("%d %d\n",ans,n-ans);}} }

?

轉載于:https://www.cnblogs.com/Loi-dfkdsmbd/articles/7701144.html

總結

以上是生活随笔為你收集整理的【hdu5285】wyh2000 and pupil的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。