AOJ2306 Rabbit Party - seica

問題文

I hate English.

考察

探索したい問題。
辺の数が少ない。
ある組み合わせに新しくウサギ(a)を招待するとき、そのウサギとの重みが０のウサギ(b)が一匹でもいるとスコアは上がらない。
その後他のウサギを招待してスコアが上がっ他としても必ずaまたはbを招待しなかったときの方が高くなる(はず)。
なので、探索は重みがあるもの同士になる。(１以上の重みで完全グラフになるっていうのかな？言葉むつかしい)
辺の数が100より、高々14匹程度なので適当に書いても行けそうな気がする。

幅探索で重複に気を付けながら重みが0なウサギが出ない間続けた。

#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<cstring>
#include<functional>
#include<stack>
#include<queue>
#include <iomanip>
#include<map>
#include<limits>
#include<cmath>
#include<algorithm>
#include<bitset>
#include<utility>
#include<complex>
#include<cstdlib>
#include<set>
#include<cctype>

#define DBG cerr << '!' << endl;
#define REP(i,n) for(int (i) = (0);(i) < (n);++i)
#define rep(i,s,g) for(int (i) = (s);(i) < (g);++i)
#define rrep(i,s,g) for(int (i) = (s);i >= (g);--(i))
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {for(int W = 0;W < (n);W++)cerr << v[W] << ' ';cerr << endl << endl;}
#define SHOW2d(v,i,j) {for(int aaa = 0;aaa < i;aaa++){for(int bbb = 0;bbb < j;bbb++)cerr << v[aaa][bbb] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(10)

using namespace std;

typedef long long ll;
typedef vector<int> iv;
typedef vector<iv> iiv;
typedef vector<string> sv;

int dist[101][101];
map<vector<int>,int> mp;

int main()
{
	int n,m;cin >> n >> m;
	
	queue<pair<vector<int>,vector<int> > > q;
	
	int ans = 0;
	
	REP(i,m)
	{
		int a,b,c;cin >> a >> b >> c;
		dist[a][b] = dist[b][a] = c;
		if(a > b)swap(a,b);
		vector<int> A = {a,b};
		vector<int> B = {c,c};
		q.push(MP(A,B));
		mp[A] = 2*c;
		ans = max(ans,2*c);
	}
	
	while(!q.empty())
	{
		pair<vector<int>,vector<int> > now = q.front();q.pop();
		vector<int> list = now.FI;
		vector<int> score = now.SE;
		for(int i = list[list.size()-1]+1;i <= n;i++)
		{
			vector<int> tmp = list;
			tmp.PB(i);
			if(mp.find(tmp) != mp.end())continue;
			vector<int> tmpscore;
			int nowscore = 0;
			int sa = 0;
			int plus = 100000000;
			
			REP(j,list.size())
			{
				int AA =  min(score[j],dist[list[j]][i]);
				nowscore += AA;
				tmpscore.PB(AA);
				sa += score[j];
				plus = min(plus,dist[list[j]][i]);
			}
			
			nowscore += plus;
			tmpscore.PB(plus);

			//cout << ' ' << nowscore << endl;
			//SHOW1d(tmp,tmp.size());
			//SHOW1d(tmpscore,tmp.size());
						
			if(plus != 0)
			{
				mp[tmp] = nowscore;
				ans = max(ans,nowscore);
				q.push(MP(tmp,tmpscore));
			}
		}
	}
	
	cout << ans << endl;

	return 0;
}

500にしては簡単かなぁ？？？