[POI2014]Tourism

题目大意：
　　给定一个$n(n\le20000)$条个点，$m(m\le25000)$条边的无向图，保证图中最长路径上的点数不超过$10$。对一个点染色的代价是$w_i$。求使得每个结点都被染色或至少有一个相邻结点被染色的最小代价。

思路：
　　由于图中最长路径上的点数不超过$10$，也就是说，对于每一个联通块的任一生成树，其最深结点的深度不超过$10$。考虑三进制状压DP，用$f[i][j]$表示深度为$i$的点，前$i$个深度状态为$j$的最小代价。其中每个状态的第$k$位为$0$则深度为$k$的结点已染色，若为$1$则表示未染色且相邻点也没有染色，若为$2$则表示未染色但是相邻结点有染色。搜索完一棵子树后将状态上传到父结点。

 #include<cstdio>

 #include<cctype>

 #include<climits>

 #include<algorithm>

 inline int getint() {

     register char ch;

     while(!isdigit(ch=getchar()));

     register int x=ch^'';

     while(isdigit(ch=getchar())) x=(((x<<)+x)<<)+(ch^'');

     return x;

 }

 const int N=,M=,K=,S=;

 const int pow[]={,,,,,,,,,,};

 bool vis[N];

 int w[N],dep[N],h[N],sz;

 unsigned f[K][S];

 struct Edge {

     int to,next;

 };

 Edge e[M];

 inline void add_edge(const int &u,const int &v) {

     e[++sz]=(Edge){v,h[u]};h[u]=sz;

     e[++sz]=(Edge){u,h[v]};h[v]=sz;

 }

 inline int bit(const int &x,const int &k) {

     return x/pow[k]%;

 }

 void dfs(const int &x,const int &d) {

     vis[x]=true;

     if((dep[x]=d)==) {

         f[][]=w[x];

         f[][]=;

         f[][]=INT_MAX;

     } else {

         std::fill(&f[d][],&f[d][pow[d+]],INT_MAX);

         for(register int i=,j=;i<pow[d];j=++i) {

             int b=;

             for(register int k=h[x];k;k=e[k].next) {

                 const int &y=e[k].to;

                 if(!vis[y]||dep[y]>=d) continue;

                 if(bit(i,dep[y])==) b=;

                 if(bit(i,dep[y])==) j+=pow[dep[y]];

             }

             f[d][i+b*pow[d]]=std::min(f[d][i+b*pow[d]],f[d-][i]);

             f[d][j]=std::min(f[d][j],f[d-][i]+w[x]);

         }

     }

     for(int i=h[x];i;i=e[i].next) {

         const int &y=e[i].to;

         if(vis[y]) continue;

         dfs(y,d+);

         for(register int i=;i<pow[d+];i++) {

             f[d][i]=std::min(f[d+][i],f[d+][i+*pow[d+]]);

         }

     }

 }

 int main() {

     const int n=getint(),m=getint();

     for(register int i=;i<=n;i++) w[i]=getint();

     for(register int i=;i<m;i++) {

         add_edge(getint(),getint());

     }

     int ans=;

     for(register int i=;i<=n;i++) {

         if(vis[i]) continue;

         dfs(i,);

         ans+=std::min(f[][],f[][]);

     }

     printf("%d\n",ans);

     return ;

 }

巴特西

[POI2014]Tourism

最新文章

热门文章