HDU3311Dig The Wells（斯坦納樹，spfa+狀態壓縮DP）可作模板

Dig The Wells

Time Limit: 6000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 1037 Accepted Submission(s): 453


Problem Description You may all know the famous story “Three monks”. Recently they find some places around their temples can been used to dig some wells. It will help them save a lot of time. But to dig the well or build the road to transport the water will cost money. They do not want to cost too much money. Now they want you to find a cheapest plan.
Input There are several test cases.
Each test case will starts with three numbers n , m, and p in one line, n stands for the number of monks and m stands for the number of places that can been used, p stands for the number of roads between these places. The places the monks stay is signed from 1 to n then the other m places are signed as n + 1 to n + m. (1 <= n <= 5, 0 <= m <= 1000, 0 <=p <= 5000)
Then n + m numbers followed which stands for the value of digging a well in the ith place.
Then p lines followed. Each line will contains three numbers a, b, and c. means build a road between a and b will cost c.

Output For each case, output the minimum result you can get in one line.
Sample Input

3 1 3
1 2 3 4
1 4 2
2 4 2
3 4 4 
4 1 4
5 5 5 5 1
1 5 1
2 5 1
3 5 1
4 5 1

Sample Output

6
5

Author dandelion
Source HDOJ Monthly Contest – 2010.02.06

【題目大意】

給定N個寺廟，和M個另外的地方。

然後給定點權，表示在這個點挖水井需要的代價。

再給定邊權，為建造無向邊i，j的代價。

然後求怎樣弄最小的代價使得前N個點，就是寺廟都能從挖的井裡得到水。

解析：因每個寺廟只需找到一口井，也就是寺廟的位置到井的位置只需一條路，所以我們的最後的最優解一定得到的是一棵樹，可以增加一個0點來連接所有的點，其邊權就是挖井的花費，所以最終以0點做為樹的根節點，這樣只要是到達0點則說明井己挖好。因任意兩個寺廟只有兩種情況（到同一口井或不同的井），到同一口井時可能最近公共父節點到井相隔幾個點。不同井則最近公共父節點一定是0點。 DP[寺廟的組成狀態][子樹的根節點]：最小花費。 dp[ j ][ i ]=min{ dp[ j ][ i ]，dp[ k ][ i ]+dp[ l ][ i ] }，其中k和l是對j的一個劃分。 dp[ j ][ i ]=min{ dp[ j ][ i ]，dp[ j ][ i' ]+w[ i' ][ i ]}，其中i和i'之間有邊相連。

#include
#include
#include
using namespace std;

#define move(a) (1<<(a))
const int N = 1010;
const int inf = 0x3fffffff;
struct EDG
{
    int v,c;
};

int n,m,dp[1<<7][N],dis[N][N];
vectormap[N];

void spfa()//求兩點之間的最短距離
{
    int inq[N]={0},ts,k;
    queueq;

    for(int s=0;s<=n+m;s++)
    {
        for(int j=0;j<=n+m;j++)
        dis[s][j]=inf;
        dis[s][s]=0;
        q.push(s);
        while(!q.empty())
        {
            ts=q.front(); q.pop();
            inq[ts]=0;
            k=map[ts].size();
            for(int j=0;jdis[s][ts]+map[ts][j].c)
                {
                    dis[s][v]=dis[s][ts]+map[ts][j].c;
                    if(!inq[v])
                    q.push(v),inq[v]=1;
                }
            }
        }
    }
}
void countDp()
{
    for(int sta=1;sta0;s=(s-1)&sta)
            if(dp[sta][i]>dp[sta^s][i]+dp[s][i])
            dp[sta][i]=dp[sta^s][i]+dp[s][i];
        }
        for(int i=0;i<=n+m;i++)
        for(int j=0;j<=n+m;j++)
            if(dp[sta][i]>dp[sta][j]+dis[j][i])
            dp[sta][i]=dp[sta][j]+dis[j][i];
    }
}
int main()
{
    int p,a,b;
    EDG e;
    while(scanf("%d%d%d",&n,&m,&p)>0)
    {
        for(int i=0;i<=n+m;i++)
        map[i].clear();

        for(int i=1;i<=n+m;i++)
        {
            scanf("%d",&e.c);
            e.v=i; map[0].push_back(e);//用挖井的花費作為i-->0邊的花費，所以最終1~n點都要歸於一點0
            e.v=0; map[i].push_back(e);
        }
        while(p--)
        {
            scanf("%d%d%d",&a,&b,&e.c);
            e.v=b; map[a].push_back(e);
            e.v=a; map[b].push_back(e);
        }
        spfa();
        countDp();
        printf("%d\n",dp[move(n+1)-1][0]);
    }
}