AOJ2403

AOJ2403

2012模擬国内予選E問題

単純な枝刈りで充分
軍事力順でソートして、残りを全て取って現状の最大値を超えられるか見る


以下、本番で提出したコード

#include <iostream>
#include <algorithm>
#include <string>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <complex>
#include <cctype>
#include <climits>

#define FOR(i, c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define each(i, c) FOR(i, c)

typedef long long int lli;

using namespace std;

const int NODE = 40 + 1;

lli p[NODE];
bool g[NODE][NODE];

int cand[NODE];
int vis[NODE];

int acc[NODE];

lli result;

void put(int n, bool b, const int node)
{
 for (int i = 0; i < node; ++i) {
   if (g[n][i]) {
     if (b) ++vis[i];
     else --vis[i];
   }
 }
 return ;
}

void rec(int i, lli sum, int node)
{
 result = max(result, sum);
 if (sum + acc[i] < result) return ;

 for (int j = i + 1; j < node; ++j) {
   const int n = cand[j];
   if (vis[n]) continue;
   put(n, true, node);
   rec(j, sum + p[n], node);
   put(n, false, node);
 }
 return ;
}

bool cmp(int a, int b)
{
 return p[a] < p[b];
}

int name(map<string, int> &m, string s)
{
 if (m.count(s)) ; else {
   int tmp = m.size();
   m[s] = tmp;
 }
 return m[s];
}

int main(void)
{
 int node;
 while (cin >> node && node) {
   fill(&g[0][0], &g[node - 1][node], false);
   fill(vis, vis + node, false);

   result = -1;

   map<string, int> M;
   for (int i = 0; i < node; ++i) {
     string a;
     int b, c;
     cin >> a >> b >> c;
     p[name(M, a)] = b;

     for (int j = 0; j < c; ++j) {
       string d;
       cin >> d;
       g[name(M, a)][name(M, d)] = true;
     }
   }

   for (int i = 0; i < node; ++i) {
     cand[i] = i;
   }
   sort(cand + 1, cand + node, cmp);
   reverse(cand + 1, cand + node);

   for (int i = 0; i < node; ++i) {
     acc[i] = 0;
     for (int j = i + 1; j < node; ++j) {
       acc[i] += p[cand[j]];
     }
   }

   put(0, true, node);
   rec(0, p[0], node);
   cout << result << endl;
 }
 return 0;
}