首页 > ACM题库 > HDU-杭电 > HDU 4085-Peach Blossom Spring-动态规划-[解题报告]HOJ
2015
04-16

HDU 4085-Peach Blossom Spring-动态规划-[解题报告]HOJ

Peach Blossom Spring

问题描述 :

The Voyages of Zheng He

Tao Yuanming(365-427) was a Chinese poet of Eastern Jin dynasty. One of his most famous works is "Peach Blossom Spring", which is a fable about a chance
discovery of an ethereal village where the people lead an ideal existence in harmony with nature, unaware of the outside world for centuries. So in Chinese, "Peach Blossom Spring" means "utopia".
In the story of "Peach Blossom Spring", there was a mysterious place. In Qin dynasty, some people escaped to that place during the civil unrest and built a village. They and their descendants never left and never had any contact with the outside world since then, until centuries latter a fisherman of Jin dynasty found them.
Recently, some Chinese ACMers happened to find the relics of the village mentioned in"Peach Blossom Spring".
They also found a document about building hiding places to escape from Qin army. The document said:
There were n houses and m roads in the village. Each road connected two houses. These houses were numbered from 1 to n. There were k families, each living in a different house.
The houses they lived were house 1, house 2, … , house k. There were also k broken houses: house n-k+1, house n-k+2, … , house n, with secret basements so that those houses could be used as hiding places.
The problem was that all roads were broken. People wanted to repair some roads so that every family could reach a hiding place through the repaired roads. Every hiding place could only hold one family. Each road cost some labor to be repaired. The head of the village wanted to find out the minimum cost way of repairing the roads, but he didn’t know how to do.
Would you solve the problem which the ancient village head never solved?

输入:

The input begins with a line containing an integer T(T<=50), the number of test cases. For each case, the first line begins with three integers —- the above mentioned n (4<=n<=50), m (0<=m<=1000) and k (1<=k<=5, 2k<=n). Then m lines follow, each containing three integers u,v and w, indicating that there is a broken road connecting house u an d v, and the cost to repair that road is w(1<=w<=1000).

输出:

The input begins with a line containing an integer T(T<=50), the number of test cases. For each case, the first line begins with three integers —- the above mentioned n (4<=n<=50), m (0<=m<=1000) and k (1<=k<=5, 2k<=n). Then m lines follow, each containing three integers u,v and w, indicating that there is a broken road connecting house u an d v, and the cost to repair that road is w(1<=w<=1000).

样例输入:

2
4 3 1
4 2 10
3 1 9
2 3 10
6 7 2
1 5 1000
2 6 1000
1 3 1
2 3 1
3 4 1
4 5 1
4 6 1

样例输出:

29
5

斯坦纳树

具体参见国家队论文

#include<cstdio>
#include<cstring>
#include<queue>
#define M 1100
#define N 55
#define INF 100000000
using namespace std;
struct Edge{
    int v,w,next;
}edge[M*2];
int head[N],cnt;
int n,m,k,K;
int st[N];
int dp[N][1100];
bool vis[N][1100];
int ans[1100];
queue<int>q;
void addedge(int u,int v,int w){
    edge[cnt].v=v;
    edge[cnt].w=w;
    edge[cnt].next=head[u];
    head[u]=cnt++;
    edge[cnt].v=u;
    edge[cnt].w=w;
    edge[cnt].next=head[v];
    head[v]=cnt++;
}
void init(){
    int i,j;
    K=1<<(2*k);
    cnt=0;
    memset(head,-1,sizeof(head));
    memset(st,0,sizeof(st));
    memset(vis,0,sizeof(vis));
    for(i=1;i<=n;i++)
        for(j=0;j<K;j++)
            dp[i][j]=INF;
    for(i=1;i<=k;i++){
        st[i]=1<<(i-1);
        dp[i][st[i]]=0;
    }
    for(i=1;i<=k;i++){
        st[n-k+i]=1<<(k+i-1);
        dp[n-k+i][st[n-k+i]]=0;
    }
}
void SPFA(){
    int i;
    while(!q.empty()){
        int x=q.front()%10000,y=q.front()/10000;
        vis[y][x]=0;
        q.pop();
        for(i=head[y];i!=-1;i=edge[i].next){
            if(dp[edge[i].v][st[edge[i].v]|x]>dp[y][x]+edge[i].w){
                dp[edge[i].v][st[edge[i].v]|x]=dp[y][x]+edge[i].w;
                if(!vis[edge[i].v][st[edge[i].v]|x] && (st[edge[i].v]|x)==x){ //st[edge[i].v]有可能为0
                    vis[edge[i].v][st[edge[i].v]|x]=1;
                    q.push(edge[i].v*10000+x);
                }
            }
        }
    }
}
void Steiner_Tree(){
    int i,j,x;
    for(i=0;i<K;i++){
        for(j=1;j<=n;j++){
            if(st[j] && (st[j]&i))continue;
            for(x=(i-1)&i;x;x=(x-1)&i)
                dp[j][i]=min(dp[j][i],dp[j][x|st[j]]+dp[j][(i-x)|st[j]]);
            if(dp[j][i]!=INF){
                q.push(j*10000+i);
                vis[j][i]=1;
            }
        }
        SPFA();
    }
}
bool check(int u){
    int r=0,i;
    for(i=0;i<k;i++){
        if(u&(1<<i))r++;
        if(u&(1<<(i+k)))r--;
    }
    return !r;
}
int main(){
    int t,T,i,j;
    int u,v,w;
    scanf("%d",&T);
    for(t=1;t<=T;t++){
        scanf("%d %d %d",&n,&m,&k);
        init();
        for(i=1;i<=m;i++){
            scanf("%d %d %d",&u,&v,&w);
            addedge(u,v,w);
        }
        Steiner_Tree();
        for(i=0;i<K;i++){
            ans[i]=INF;
            for(j=1;j<=n;j++)
                ans[i]=min(ans[i],dp[j][i]);
        }
        for(i=0;i<K;i++)
            if(check(i))
                for(j=(i-1)&i;j;j=(j-1)&i)
                    if(check(j))
                        ans[i]=min(ans[i],ans[j]+ans[i-j]);
        if(ans[K-1]==INF)printf("No solution\n");
        else printf("%d\n",ans[K-1]);
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/waitfor_/article/details/8024411


  1. 代码是给出了,但是解析的也太不清晰了吧!如 13 abejkcfghid jkebfghicda
    第一步拆分为 三部分 (bejk, cfghi, d) * C(13,3),为什么要这样拆分,原则是什么?