首页 > 代码库 > poj2531
poj2531
看了一下0ms,16ms,100ms左右过了的代码,思维量对我来说比较大,不是很容易理解。
我的作法:
用并查集算权值和。
用dfs枚举两个点集的所有可能,由于是完全图,枚举一半的点即可。
#include<iostream> #include<cstring> using namespace std; int map[30][30],N,vis[30],MAX; void getdate() { int i,j; scanf("%d",&N); for(i=0;i<N;i++) for(j=0;j<N;j++) scanf("%d",&map[i][j]); } void dfs(int start,int v2) { int i,j,sum; if(v2==0) { sum=0; for(i=0;i<N;i++) if(vis[i]==1) for(j=0;j<N;j++) if(vis[j]==0) sum+=map[i][j]; MAX=max(MAX,sum); return; } for(i=start;i<N&&i+v2<=N;i++) if(vis[i]==0) { vis[i]=1; dfs(i+1,v2-1); vis[i]=0; } } void solve() { int i,m; getdate(); m=N/2; MAX=-1; memset(vis,0,sizeof(vis)); for(i=1;i<=m;i++) dfs(0,i); printf("%d\n",MAX); } int main() { solve(); }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。