Description
我的灵魂与我之间的距离如此遥远，而我的存在却如此真实。
——加缪《局外人》
我醒来的时候，发现满天星斗照在我的脸上。田野上的声音一直传到我的耳畔。夜的气味，土地的气味，海盐的气味，使我的两鬓感到清凉。这沉睡的夏夜的奇妙安静，像潮水一般浸透我的全身。这时，长夜将尽，汽笛叫了起来。它宣告有些人踏上旅途，要去一个从此和我无关痛痒的世界。
这时我在想一个问题：我有一个n个点，m条边的无向图，第i个点建立一个旅游站点的费用是c_i。特别地，这张图中的任意两点间不存在节点数超过10的简单路径。
为了把一切都做得完善，为了使我感到不那么孤独，我想要建造一些旅游站点使得每个点要么建立了旅游站点，要么与它有边直接相连的点里至少有一个点建立了旅游站点。我还希望这个建造方案总花费尽量少。
请求出这个花费。
Solution
题目里那个奇怪的条件就是告诉你，这张图生成的dfs树的深度不会超过10，
那么就很自然的想到了状压DP，
设f[i][s]表示做到了第i层，状态为S，S是一个3进制数，0表示没有选但被覆盖到了，1表示选了，2表示没有选且没有被覆盖到，
转移显然，
复杂度：注意，并不是
复杂度仔细算！！！仔细算！！！仔细算！！！
Code
#include <cstdio>
#include <algorithm>
#include <cstring>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fod(i,a,b) for(int i=a;i>=b;i--)
#define efo(i,q) for(int i=A[q];i;i=B[i][0])
#define min(q,w) ((q)<(w)?(q):(w))
using namespace std;
const int N=200500,INF=2139062143;
int read(int &n)
{
scanf("%d",&n);
return n;
}
int n,m,ans;
int co[N],C[N];
bool z[N];
int B[3*N][2],A[N],B0;
int er[20];
int f[15][1772000];
void link(int q,int w)
{
B[++B0][0]=A[q],A[q]=B0,B[B0][1]=w;
B[++B0][0]=A[w],A[w]=B0,B[B0][1]=q;
}
bool OK(int q,int w)
{
for(;q;q/=3,w/=3)if(q%3==1&&w%3)return 1;
return 0;
}
int JA(int q,int w,int n)
{
fo(i,1,n)if((q/er[i])%3==2&&(w/er[i])%3)q-=2*er[i];
return q;
}
void dfs(int q,int c)
{
int t=er[c];
efo(i,q)if(C[B[i][1]])if((t/er[C[B[i][1]]])%3==0)t+=er[C[B[i][1]]];
C[q]=c;
fo(i,0,er[c]-1)if(f[c-1][i]<INF)
{
if(OK(i,t))f[c][i]=f[c-1][i];
else f[c][i+2*er[c]]=f[c-1][i];
int t1=JA(i,t,c-1)+er[c];
f[c][t1]=min(f[c][t1],f[c-1][i]+co[q]);
}
efo(i,q)if(!C[B[i][1]])
{
dfs(B[i][1],c+1);
fo(j,0,er[c+1]-1)
{
f[c][j]=min(f[c+1][j],f[c+1][j+er[c+1]]);
f[c+1][j]=f[c+1][j+er[c+1]]=f[c+1][j+er[c+1]*2]=INF;
}
}
}
int main()
{
freopen("absurdity.in","r",stdin);
freopen("absurdity.out","w",stdout);
int q,w;
er[1]=1;fo(i,2,15)er[i]=er[i-1]*3;
read(n),read(m);
fo(i,1,n)read(co[i]);
fo(i,1,m)read(q),read(w),link(q,w);
ans=0;
memset(f,127,sizeof(f));
memset(f[0],0,sizeof(f[0]));
fo(i,1,n)if(!C[i])
{
dfs(i,1);
ans+=min(f[1][0],f[1][1]);
f[1][0]=f[1][1]=f[1][2]=INF;
}
printf("%d\n",ans);
return 0;
}