hihoCoder #1179 : 永恒游戏 (暴力枚举)

题意：

　　给出一个有n个点的无向图，每个点上有石头数个，现在的游戏规则是，设置某个点A的度数为d，如果A点的石子数大于等于d，则可以从A点给每个邻接点发一个石子。如果游戏可以玩10万次以上，输出INF，否则输出最多能玩几次。

思路：　　

　　暴力枚举每个可以玩的点，假如可以玩无限次，且当前状态为Z（指所有点的石头数的序列作为一个状态），那么在玩了多次之后，一定会造成循环，也就是说，玩几次之后，每个点的石子数和初始的石子数一模一样，这样子我再重复之前是怎么玩的就可以无限玩了。但是由于有200个点，所以玩一次就去判断是否和初始一样的状态，否则复杂度为 O(100000*结点数*该结点的边数)，数量级上亿。

　　现在只需要枚举10万次就知道结果了，不用去判断其他的。而且每次选择要玩的点都可以任意选，只要满足了条件（并不需要先玩石子数多的，或少的）。

 #include <bits/stdc++.h>

 #define LL long long

 using namespace std;

 const int N=;

 int n, m, a, b, num[N];

 vector< vector<int> >   vect;

 unordered_set<int> sett;

 int cal()

 {

     int cnt=;

     for(int i=; i<n; i++)    if(num[i]>=vect[i].size())    sett.insert(i);    //符合条件

     while(!sett.empty())

     {

         cnt++;              //一次

         if(cnt>=) return cnt;

         int q=*sett.begin();

         num[q]-=vect[q].size();

         if(num[q]<vect[q].size())  sett.erase(sett.begin()); //这个点已经不能再玩了

         for(int i=; i<vect[q].size(); i++) //往邻居加石头

         {

             int p=vect[q][i];  //栈顶结点所连的点

             num[p]++;

             if(num[p]>=vect[p].size() ) sett.insert(p);

         }

     }

     return cnt;

 }

 int main()

 {

     //freopen("e://input.txt", "r", stdin);

     scanf("%d%d",&n,&m);

     for(int i=; i<n; i++) scanf("%d", &num[i]); //石头数

     vect.resize(n);

     for(int i=; i<m; i++)

     {

         scanf("%d%d", &a, &b);    //输入边，无向图

         vect[a].push_back(b);

         vect[b].push_back(a);

     }

     int ans=cal();

     if(ans>=)     printf("INF\n");

     else                printf("%d\n",ans);

     return ;

 }

AC代码

巴特西

hihoCoder #1179 : 永恒游戏 (暴力枚举)

最新文章

热门文章