记录一个菜逼的成长。。
令dp[s]为子图S已经染色的最少染色数，那么有dp[s]=min(dp[s],dp[s^s0]+1)其中s0是S的独立子集，可以全部染成一种颜色。
#include <cstdio> #include <iostream> #include <cstring> #include <string> #include <algorithm> #include <cstdlib> #include <vector> #include <set> #include <map> #include <queue> #include <stack> #include <list> #include <deque> #include <cctype> #include <bitset> #include <cmath> using namespace std; #define ALL(v) (v).begin(),(v).end() #define cl(a) memset(a,0,sizeof(a)) #define fin freopen("D://in.txt","r",stdin) #define fout freopen("D://out.txt","w",stdout) #define lson t<<1,l,mid #define rson t<<1|1,mid+1,r #define seglen (node[t].r-node[t].l+1) typedef long long LL; typedef unsigned long long ULL; typedef unsigned int UI; typedef pair<int,int> PII; typedef pair<LL,LL> PLL; typedef vector<PII> VPII; const int INF = 0x3f3f3f3f; const int MOD = 1e9 + 7; template <typename T> inline void read(T &x){ T ans=0; char last=' ',ch=getchar(); while(ch<'0' || ch>'9')last=ch,ch=getchar(); while(ch>='0' && ch<='9')ans=ans*10+ch-'0',ch=getchar(); if(last=='-')ans=-ans; x = ans; } inline bool DBread(double &num) { char in;double Dec=0.1; bool IsN=false,IsD=false; in=getchar(); if(in==EOF) return false; while(in!='-'&&in!='.'&&(in<'0'||in>'9')) in=getchar(); if(in=='-'){IsN=true;num=0;} else if(in=='.'){IsD=true;num=0;} else num=in-'0'; if(!IsD){ while(in=getchar(),in>='0'&&in<='9'){ num*=10;num+=in-'0';} } if(in!='.'){ if(IsN) num=-num; return true; }else{ while(in=getchar(),in>='0'&&in<='9'){ num+=Dec*(in-'0');Dec*=0.1; } } if(IsN) num=-num; return true; } template <typename T> inline void write(T a) { if(a < 0) { putchar('-'); a = -a; } if(a >= 10) write(a / 10); putchar(a % 10 + '0'); } /******************head***********************/ const int maxn = 20; UI dp[1<<18],du[1<<18]; char s[maxn][maxn]; int main() { int T;read(T); while(T--){ int n; read(n); for( int i = 0; i < n; i++ ) scanf("%s",s[i]); //判断每一个子集是不是独立集 for( int i = 0; i < (1 << n); i++ ){ int flag = 1; for( int j = 0; j < n; j++ ){ for( int k = j + 1; k < n; k++ ){ //如果两个点之间有边，则不是独立集 if(((1<<j)&i)&&((1<<k)&i)&&s[j][k] == '1'){ flag = 0; goto to;//这里需要退出循环,否则会吃T; } } } to:du[i] = flag; } UI ans = 0,tmp = 1;//ans 为 unsigned可以自动取模 dp[0] = 0; for( int i = 1; i < (1<<n); i++ ){ dp[i] = INF; //对每一个子集枚举它的独立子集，每一个子集的色数是除了它的独立子集的色数加1，取最小值 for( int j = i; j; j = (j-1)&i){//枚举子集的循环 if(du[j]){ dp[i] = min(dp[i],dp[i^j] + 1);//dp[i^j] 就是这个子集除了独立子集之外的色数 } } tmp *= 233; ans += tmp * dp[i]; } write(ans); puts(""); } return 0; }