Aizu 2306 Rabbit Party DFS
题目链接:
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2306
题意:
给定n个点的完全图，下面给出m条边权不为0的边
下面m行给出边和边权。
其他的边边权都为0.
选择一个点集出来，点权是这个点连接这个点集的边权最小值
找一个这样的子图使得点权和最大，输出点权和。
题解:
最后选出来的点，一定是由那m个边所组成的完全图
因为是一个完全图，所以我们选择的点构成的图一定不包含权值为0的边。因为若包含了权值为0的边，则大可以把这两点删掉而不会减小答案。
所以我们选择的图中的边一定只 包含给出的m条边，且由这m条边构成的一个团。
只有100个边，所以最多就是14个点的完全图
即 n*(n-1)/2 <= 100 => n <=14
所以爆搜这14个点就可以了
代码:
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 #define MS(a) memset(a,0,sizeof(a)) 5 #define MP make_pair 6 #define PB push_back 7 const int INF = 0x3f3f3f3f; 8 const ll INFLL = 0x3f3f3f3f3f3f3f3fLL; 9 inline ll read(){ 10 ll x=0,f=1;char ch=getchar(); 11 while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} 12 while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} 13 return x*f; 14 } 15 ////////////////////////////////////////////////////////////////////////// 16 const int maxn = 1e5+10; 17 18 int n,m,mp[105][105],vis[105],ans; 19 vector<int> Q; 20 21 void dfs(int u){ 22 int tmp = 0; 23 for(int i=0; i<(int)Q.size(); i++){ 24 int minn = INF; 25 for(int j=0; j<(int)Q.size(); j++){ 26 if(i!=j) minn = min(minn,mp[Q[i]][Q[j]]); 27 } 28 if(minn == INF) 29 minn = 0; 30 tmp += minn; 31 } 32 ans = max(ans,tmp); 33 34 for(int v=u+1; v<=n; v++){ 35 if(vis[v]) continue; 36 int flag = 1; 37 for(int j=0; j<(int)Q.size(); j++){//如果v没有与当前选的点集有权边，v就一定不在要选的点集中 38 if(mp[v][Q[j]] == 0) { 39 flag = 0; 40 break; 41 } 42 } 43 44 if(flag){ 45 vis[v] = 1; // 选v 46 Q.push_back(v); 47 dfs(v); 48 vis[v] = 0; // 不选v 因为 选v可能使得答案变小 49 Q.pop_back(); 50 } 51 } 52 } 53 54 int main(){ 55 n=read(), m=read(); 56 for(int i=0; i<m; i++){ 57 int u,v,w; scanf("%d%d%d",&u,&v,&w); 58 mp[u][v]=mp[v][u]=w; 59 } 60 61 for(int i=1; i<=n; i++){ 62 vis[i] = 1; 63 Q.push_back(i); // 枚举肯定选哪个点的情况 64 dfs(0); 65 Q.pop_back(); 66 vis[i] = 0; 67 } 68 69 cout << ans << endl; 70 71 return 0; 72 }