I.营养需求

I.营养需求

题意

给定$n$块地，$m$头牛，每头牛有两个喜爱的地，要给$m$块地染色$col\in[1,4]$，每头牛喜爱的两块地颜色要求不同，输出字典序最小的染色方案。

思路

贪心$+$暴力

从第一块地开始贪心地染色，然后暴力从小到大枚举染的颜色，特判$m$头牛是否满足条件，特判时只要判较小的那块地，后面未染色的地可以不用管。

时间复杂度：$O(4nm)$

代码

#include<bits/stdc++.h>
using namespace std;
const int N=200;
typedef pair<int,int> PII;
#define fi first
#define se second
PII a[N];
int ans[N],n,m;
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d",&a[i].fi,&a[i].se);
        if(a[i].fi>a[i].se) swap(a[i].fi,a[i].se);
    }
    for(int i=1;i<=n;i++){
        int f;
        for(int j=1;j<=4;j++){
             f=j;
            for(int k=1;k<=m;k++){
                if(a[k].se==i&&ans[a[k].fi]==j){
                    f=0;break;
                }
            }
            if(f) break;
        }
        ans[i]=f;
    }
    for(int i=1;i<=n;i++) printf("%d",ans[i]);
    return 0;
}