首页 > 代码库 > topcoder srm 696 div1 -3
topcoder srm 696 div1 -3
1、给定一个50个节点的无向图，有$m$条边。现在以任意一种序列对每个节点染色。染当前节点的代价为染色完当前节点后满足两个端点都被染色的边的数量。求最小的染色代价。$m \leq 20$
思路：一个直观的思路是应该先染色度数小的节点。由于$m\leq 20$，所以如果先把那些孤立的点以及那些度数为1但是其相连的另一端还未染色的节点先染色，那么剩下还未染色的节点数不会超过20。而且已经染色的节点代价都为0.令$c_{s}$表示将状态为$s$的节点全部染色时最后一步的代价。$f_{i}$表示将状态$i$全部染色的代价，那么$f_{i}=min(f_{t}+c_{i})$，其中$t=i$^$2^{j}$且$i$&$2^{j}\neq 0$,即最后染色节点$j$
#include <iostream>#include <stdio.h>#include <cstdlib>#include <algorithm>#include <cmath>#include <string.h>#include <set>#include <vector>#include <time.h>#include <queue>#include <stack>#include <map>#include <assert.h>using namespace std;const int N=50;int h[N];int a[N],aNum;int d[N];int cost[1<<23];int dp[1<<23];int GetCost(const int Mask,const vector<int>& Ex,const vector<int>& Ey){ int p[N]; memset(p,0,sizeof(p)); for(int i=0;i<50;++i) { if(h[i]) p[i]=1; else if(Mask&(1<<a[i])) p[i]=1; } int nNum=0; const int m=(int)Ex.size(); for(int i=0;i<m;++i) { if(p[Ex[i]]&&p[Ey[i]]) ++nNum; } return nNum;}class Gperm{public: int countfee(vector<int> x,vector<int> y) { const int m=(int)x.size(); const int n=50; for(int i=0;i<m;++i) ++d[x[i]],++d[y[i]]; for(int i=0;i<n;++i) { if(0==d[i]) h[i]=1; else if(1==d[i]) { int j; for(int k=0;k<m;++k) { if(x[k]==i) j=y[k]; else if(y[k]==i) j=x[k]; } if(!h[j]) h[i]=1; } } for(int i=0;i<n;++i) if(!h[i]) a[i]=aNum++; for(int i=0;i<(1<<aNum);++i) cost[i]=GetCost(i,x,y); memset(dp,-1,sizeof(dp)); dp[0]=0; for(int i=1;i<(1<<aNum);++i) { for(int j=0;j<aNum;++j) if(i&(1<<j)) { int tmp=dp[i^(1<<j)]+cost[i]; if(dp[i]==-1||tmp<dp[i]) dp[i]=tmp; } } return dp[(1<<aNum)-1]; }};
topcoder srm 696 div1 -3
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。