hihocoder〓〓1179:永遠のゲーム暴力

シシ1179:永遠のゲーム
Time Limit:20 Sec
メモリLimit:256 MB
タイトル接続
http://hihocoder.com/problemset/problem/1179
Description
昔、Rowdarkがまだ善良な魔法使いである時、彼はn個の点mの辺の無向絵でゲームをしました.
彼は最初にいくつかの点に石を置いた.Rowdarkは毎回、ポイントAを選択し、ポイントA上の石の数が隣のポイントの数より大きいことを要求する.その後、Aの各隣のBに対して、Aの上の石をBに移します.このような点Aが選べないとゲームは終了します.Rowdarkはこのゲームが無限ループするかどうかを知りたいです.問題をもっと簡単にするためには、10万ラウンド後もゲームを続けているかどうかを求めるだけです.
Input
1行目は2つの整数nとm(1≦n≦200)です.
第二行n個の整数a 0,a 1...an-1は、各点における砂利の個数(0≦ai≦109)を表します.
次のm行は、各行の2つの数xとy(x≠y、0≦x、y≦n-1)で、xとyの間に辺があることを表します.問題は重くないことを保証します.そして、どの点にも隣があります.
Output
Rowdarkが100000ラウンドを超えたら、INFを出力します.そうでなければ最大ステップ数を出力します.
Sample Input
3 31 2 10 11 22 0
Sample Output
INF
HINT
 
題意
 
クイズ:
毎回、残りの権利が一番多い点を暴力的に選択すればいいです.すべての点の権利がこの点の度数より小さいなら、私達は-1を出力します.
コード:
 

#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <sstream>
#include <queue>
#include <typeinfo>
#include <fstream>
#include <map>
#include <stack>
typedef long long ll;
using namespace std;
//freopen("D.in","r",stdin);
//freopen("D.out","w",stdout);
#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)
#define test freopen("test.txt","r",stdin)
#define maxn 100001
#define mod 10007
#define eps 1e-9
const int inf=0x3f3f3f3f;
const ll infll = 0x3f3f3f3f3f3f3f3fLL;
inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
//**************************************************************************************

vector<int> g[210];
long long a[210];
int deg[210];

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) 
    {
        scanf("%lld", &a[i]);
    }
    for (int i = 0; i < m; i++) 
    {
        int u, v;
        scanf("%d%d", &u, &v);
        g[u].push_back(v);
        g[v].push_back(u);
        deg[u]++;
        deg[v]++;
    }
    for (int i = 0; i <= 100000; i++) 
    {
        int id = -1;
        for (int i = 0; i < n; i++) 
        {
            if (a[i] >= deg[i]) 
            {
                if (id == -1 || (a[i] - deg[i]) > (a[id] - deg[id])) 
                {
                    id = i;
                }
            }
        }
        if (id == -1) 
        {
            printf("%d
", i);
            return 0;
        } 
        else 
        {
            for (int i = 0; i < g[id].size(); i++) 
            {
                a[id]--;
                int v = g[id][i];
                a[v]++;
            }
        }
    }
    puts("INF");
    return 0;
}