题目：https://www.lydsy.com/JudgeOnline/problem.php?id=4006
除了模板，就是记录 ans[ s ] 表示 s 合法的最小代价。合法即保证 s 里同一种的连通，整体可以不连通。ans[ ] 也枚举子集转移即可，初值就是模板算出来的 dp[ ][ s ] 最小值。
#include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; int rdn() { int ret=0;bool fx=1;char ch=getchar(); while(ch>'9'||ch<'0'){if(ch=='-')fx=0;ch=getchar();} while(ch>='0'&&ch<='9')ret=ret*10+ch-'0',ch=getchar(); return fx?ret:-ret; } int Mn(int a,int b){return a<b?a:b;} int Mx(int a,int b){return a>b?a:b;} const int N=1005,M=3005,K=15,Lm=(1<<10)+5,INF=6e7+5; int n,m,cnt,hd[N],xnt,to[M<<1],nxt[M<<1],w[M<<1]; int col[K],dy[K],tot,ct[K],bin[K]; int dp[N][Lm],ans[Lm];bool b[Lm],ins[N]; queue<int> q; void add(int x,int y,int z){to[++xnt]=y;nxt[xnt]=hd[x];hd[x]=xnt;w[xnt]=z;} void b_init() { for(int s=0;s<bin[cnt];s++) { int tct[K]={0}; for(int i=0;i<cnt;i++) if(s&bin[i])tct[col[i+1]]++; b[s]=1; for(int i=1;i<=tot;i++)if(tct[i]&&tct[i]<ct[i]){b[s]=0;break;} } } void spfa(int s) { for(int i=1;i<=n;i++)q.push(i),ins[i]=1; while(q.size()) { int k=q.front();q.pop();ins[k]=0; for(int i=hd[k],v;i;i=nxt[i]) if(dp[v=to[i]][s]>dp[k][s]+w[i]) { dp[v][s]=dp[k][s]+w[i]; if(!ins[v])q.push(v),ins[v]=1; } } } int main() { n=rdn();m=rdn();cnt=rdn(); for(int i=1,u,v,z;i<=m;i++) u=rdn(),v=rdn(),z=rdn(),add(u,v,z),add(v,u,z); memset(dp,0x3f,sizeof dp); bin[0]=1;for(int i=1;i<=cnt;i++)bin[i]=bin[i-1]<<1; for(int i=1;i<=cnt;i++) { int c=rdn();int d=rdn(); if(!dy[c])dy[c]=++tot; col[i]=dy[c]; ct[col[i]]++; dp[d][bin[i-1]]=0;//[d]not[i] } b_init(); memset(ans,0x3f,sizeof ans); for(int s=0;s<bin[cnt];s++) { for(int i=1;i<=n;i++) for(int d=(s-1)&s;d;d=(d-1)&s) dp[i][s]=Mn(dp[i][s],dp[i][d]+dp[i][s^d]); spfa(s); for(int i=1;i<=n;i++)ans[s]=Mn(ans[s],dp[i][s]); } for(int s=0;s<bin[cnt];s++) { if(!b[s])continue; for(int d=(s-1)&s;d;d=(d-1)&s) if(b[d])ans[s]=Mn(ans[s],ans[d]+ans[s^d]); } printf("%d ",ans[bin[cnt]-1]); return 0; }