\(1\) 和 \(3\) 是一样的。做法就是二分图和分组背包。小蒟蒻犯了普通人难以想象的错误(如下),调了 \(20\) 分钟!
#include <bits/stdc++.h>
using namespace std;
//Start
typedef long long ll;
typedef double db;
#define mp(a,b) make_pair(a,b)
#define x(a) a.first
#define y(a) a.second
#define b(a) a.begin()
#define e(a) a.end()
#define sz(a) int((a).size())
#define pb(a) push_back(a)
const int inf=0x3f3f3f3f;
const ll INF=0x3f3f3f3f3f3f3f3f;
//Data
const int N=5e3,M=1e5;
vector<int> e[N+7];
int f[N+7][N+7],mk[N+7];
//Dfs
int d[N+7],ct[N+7],co[3][N+7];
void Dfs(int u,int t,int cn){
d[u]=t,ct[u]=cn,co[t][cn]++;
for(int v:e[u])
if(!d[v]) Dfs(v,3-t,cn); //二分图染色
else if(d[u]+d[v]!=3) puts("NO"),exit(0); //不是二分图
}
//Main
int main(){
int n,m; scanf("%d%d",&n,&m);
int a,b,c; scanf("%d%d%d",&a,&b,&c);
for(int i=1;i<=m;i++){
int u,v; scanf("%d%d",&u,&v);
e[u].pb(v),e[v].pb(u);
}
int w=0;
f[0][0]=1;
for(int i=1;i<=n;i++)if(!d[i]){
Dfs(i,1,++w);
for(int j=n;j>=0;j--){
if(j+co[1][w]<=n&&f[w-1][j]) f[w][j+co[1][w]]=1;
if(j+co[2][w]<=n&&f[w-1][j]) f[w][j+co[2][w]]=1; // 分组背包
}
}
if(!f[w][b]) return puts("NO"),0;
else puts("YES");
for(int i=w,j=b;i>=1;i--){
if(j-co[1][i]>=0&&f[i-1][j-co[1][i]]) mk[i]=1,j-=co[1][i];
else if(j-co[2][i]>=0&&f[i-1][j-co[2][i]]) mk[i]=2,j-=co[2][i]; //回溯
//if(j-co[1][i]>=0&&f[i-1][j-co[1][i]]) mk[i]=1,j-=co[1][i];
//if(j-co[2][i]>=0&&f[i-1][j-co[2][i]]) mk[i]=2,j-=co[2][i];
/*
原来是这么写的,没想到前面j-=co[1][i]会影响这里!!!
*/
}
for(int i=1;i<=n;i++)
if(mk[ct[i]]==1){
if(d[i]==1) printf("2");
else {
if(a) printf("1"),a--;
else printf("3");
}
} else {
if(d[i]==2) printf("2");
else {
if(a) printf("1"),a--;
else printf("3");
}
}
puts("");
return 0;
}
祝大家学习愉快!