[Usaco2019 Feb]The Great Revegetation

题目：

The Great Revegetation
(grass.cpp/in/out 1s 256M)
长时间的干旱使得Farmer John的N块草地上牧草匮乏。随着雨季即将到来，现在应当是重新种植的时候了。在Farm
er John的储物棚里有四个桶，每个桶里装着一种不同的草种。他想要在每块草地上播种其中一种草。作为一名奶
农，Farmer John想要确保他的每头奶牛都能得到丰富的食谱。他的M头奶牛每一头都有两块喜爱的草地，他想要确
保这两块草地种植不同种类的草，从而每头奶牛都可以有两种草可供选择。Farmer John知道没有一块草地受到多
于3头奶牛的喜爱。
请帮助Farmer John选择每块草地所种的草的种类，使得所有奶牛的营养需求都得到满足。
Input
输入的第一行包含N（2≤N≤100）和M（1≤M≤150）。
以下M行，每行包含两个范围为1…N的整数，为Farmer John的一头奶牛喜欢的两块草地。
Output
输出一个N位数，每一位均为1…4之一，表示每一块草地上所种的草的种类。
第一位对应草地1的草的种类，第二位对应草地2，以此类推。如果有多种可行的解，只需输出所有解中最小的N位数。
Sample Input
5 6
4 1
4 2
4 3
2 5
1 2
1 5
Sample Output
12133

法一：

递归dfs，不断查找当前位数可摆放的最小值。

先排序，保证从上到下，从左至右为递增状态。

k表示位数，side表示当前可摆放的最小值

flag[k][i]表示第k位上能否放i这个数

如果左边的值已经放好了，那么右边的就不能放左边的值了，flag[node[u].y][ans]=false;

因为草地的种类和在[1,N]之间，所以判断当前最小值是否为当前的位数(保证第一位即为1)

code:

 1 #include<bits/stdc++.h>
 2 #define ll long long
 3 #define fill(a,b) memset(a,b,sizeof(a))
 4 using namespace std;
 5 bool flag[2100][5];
 6 int n,m;
 7 struct kk{int x,y;}node[2100];
 8 int cmp(kk A,kk B){return A.x<B.x;}
 9 void dfs(int k,int side){
10     int u=0,ans;
11     if (k>n) return ;
12     for (int i=1;i<=4;i++)
13         if (flag[k][i]){ans=i;break;}
14     printf("%d",ans);
15     for (u=side;node[u].x==k;u++){
16         flag[node[u].y][ans]=false;
17     }
18     dfs(k+1,u);
19 }
20 int main(){
21     //freopen("grass.in","r",stdin);
22     //freopen("grass.out","w",stdout);
23     scanf("%d%d",&n,&m);
24     fill(flag,true);
25     for (int i=1;i<=m;i++){
26         scanf("%d%d",&node[i].x,&node[i].y);
27         if (node[i].x>node[i].y) swap(node[i].x,node[i].y);
28     }
29     sort(node+1,node+m+1,cmp);
30     dfs(1,1);
31     return 0;
32 }/*
33 6 6
34 1 2
35 2 3
36 3 4
37 4 5
38 1 5
39 1 6
40 */

法二：

类似于法一，直接三个for循环模拟

code:

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int main()
 4 {
 5   int N, M;
 6   int A[151], B[151], G[101];
 7   cin >> N >> M;
 8   for (int i=0; i<M; i++) { 
 9     cin >> A[i] >> B[i];
10     if (A[i] > B[i]) swap (A[i], B[i]);
11   }
12   for (int i=1; i<=N; i++) {
13       int g;
14     for (g = 1; g <= 4; g++) {
15       bool ok = true;
16       for (int j=0; j<M; j++){
17         if (B[j] == i && G[A[j]] == g){
18          ok = false;
19                  
20         }
21         //cout<<"G[A[j]]= "<<G[A[j]]<<" g= "<<g<<" i= "<<i<<" j= "<<j<<" A[j]= "<<A[j]<<" B[j]= "<<B[j]<<endl;
22     }
23       if (ok) break;
24     }
25     G[i] = g;
26     //cout<<"G[i]= "<<G[i]<<endl;
27     cout << g;
28   }
29   cout << "
";
30   return 0;
31 }