題目鏈接：點擊查看
題目大意：給出一個由 n 個點和 m 條邊組成的無向圖，要求給 n 個點賦值為 1 、 2 或 3 ，需要滿足以下條件：
每個點都需要被賦值權值為 1 的點共 n1 個權值為 2 的點共 n2 個權值為 3 的點共 n3 個對于每個點 u 以及其子節點 v 需要滿足 abs( val[ u ] - val[ v ] ) == 1
先判斷是否存在可行方案，如果存在，給出任意一種構造方案
題目分析：首先需要轉換題意，題目中的條件 1 是廢話，關鍵是先要判斷能否滿足條件 5 ，仔細想一下，如果滿足條件的話，那么權值為 1 的點一定不能和權值為 3 的點連邊，換句話說，整張圖就被分成了一張二分圖，一邊賦值為 2 ，另一邊賦值為 1 或 3 都可以，所以第一步是需要用dfs判斷圖中是否存在奇環，以確定是否為二分圖，如果不是二分圖的話就肯定無解，如果是的話進入下一步判斷
因為題目給出的圖并不是一張連通圖，所以我們需要判斷所有連通塊是否存在一種分配方法，可以讓 n2 個權值為 2 的點恰好分配完畢，這個可以利用完全背包的思想，dp[ i ][ j ] 代表到了第 i 個連通塊，可以分配恰好 j 個權值為 2 的點是否可行，最后根據 dp[ cnt ][ n2 ] 就可以判斷是否存在解了，其中 cnt 是連通塊的個數
如果存在解的話，我們可以先對權值為 2 的點進行分配，最后沒有被分配到的點顯然分配上 1 或 3 就行了
關于 dp 的轉移和分配，可以參考前段時間的一道題目：
CodeForces - 1341D
代碼：
?
#include<iostream>
#include<cstdio>
#include<string>
#include<ctime>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<stack>
#include<climits>
#include<queue>
#include<map>
#include<set>
#include<sstream>
using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=5e3+100;vector<int>node[N],pos[N][3];int c[N],cnt,ans[N];bool dp[N][N];bool dfs(int u,int color)
{c[u]=color;pos[cnt][color].push_back(u);for(auto v:node[u]){if(c[v]==0){if(!dfs(v,3-color))return false;}else if(c[v]==color)return false;}return true;
}int main()
{
#ifndef ONLINE_JUDGE
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
#endif
// ios::sync_with_stdio(false);int n,m,n1,n2,n3;scanf("%d%d%d%d%d",&n,&m,&n1,&n2,&n3);while(m--){int u,v;scanf("%d%d",&u,&v);node[u].push_back(v);node[v].push_back(u);}bool flag=true;for(int i=1;i<=n;i++)if(c[i]==0){cnt++;if(!dfs(i,1)){flag=false;break;}}if(!flag)return 0*puts("NO");dp[0][0]=true;for(int i=1;i<=cnt;i++){int sz1=pos[i][1].size(),sz2=pos[i][2].size();for(int j=0;j<=n2;j++){if(j>=sz1)dp[i][j]|=dp[i-1][j-sz1];if(j>=sz2)dp[i][j]|=dp[i-1][j-sz2];}}if(!dp[cnt][n2])puts("NO");else{puts("YES");for(int i=cnt;i>=1;i--){int sz1=pos[i][1].size(),sz2=pos[i][2].size();if(n2-sz1>=0&&dp[i-1][n2-sz1])//顏色為 1 的地方放數字 2 {n2-=sz1;for(int j=0;j<pos[i][1].size();j++)ans[pos[i][1][j]]=2; }else//顏色為 2 的地方放數字 2 {n2-=sz2;for(int j=0;j<pos[i][2].size();j++)ans[pos[i][2][j]]=2; }}for(int i=1;i<=n;i++){if(ans[i])printf("%d",ans[i]);else{if(n1){n1--;putchar('1');}elseputchar('3');}}}return 0;
}
?
總結
以上是生活随笔為你收集整理的CodeForces - 1354E Graph Coloring(dfs判断二分图+dp)的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
