The 2019 ICPC China Nanchang National Invitational and International Silk-Road Programming Contest-A.Attack(斯坦纳树)

题目链接:The 2019 ICPC China Nanchang National Invitational and International Silk-Road Programming Contest-A.Attack

题意:

给n个点,m条无向边,然后要求四对点相连通,问最小花费。

题解:

斯坦纳树。

首先用dp(i,j)表示以i点为根,连通性为j的时候在最小花费,j为一个二进制数。因为点数较多,但是要求相连的点数较少,所以我们可以用j表示需要相连的点的连通性。

然后两重转移:

第一步:dp(i,j)=min(dp(i,j),dp(i,k)+dp(i,j-k)),k为集合j的一个划分,通过枚举子集转移即可。

第二步:dp(v,j)=min(dp(v,j),dp(u,j)+w(u,v)),通过SPFA转移。

因为我们的j只表示了8个点的状态,所以还需要对这些状态进行dp,取最优解。

参考代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e2 + 10;
const int MAXM = 1e3 + 10;
const int inf = 0x3f3f3f3f;
int n, m;
map<string, int> mp;
struct EDGE
{
    int v, w, nxt;
} edge[MAXM << 1];
int ecnt = 0, fir[MAXN];
void addedge(int u, int v, int w)
{
    edge[ecnt].v = v;
    edge[ecnt].w = w;
    edge[ecnt].nxt = fir[u];
    fir[u] = ecnt++;
}
int dis[50][1 << 8];
queue<int> que;
bool used[MAXN];
void spfa(int sta)
{
    while (!que.empty())
    {
        int u = que.front();
        que.pop();
        used[u] = 0;
        for (int i = fir[u]; i != -1; i = edge[i].nxt)
        {
            int v = edge[i].v;
            int w = edge[i].w;
            if (dis[v][sta] > dis[u][sta] + w)
            {
                dis[v][sta] = dis[u][sta] + w;
                if (!used[v])
                {
                    used[v] = 1;
                    que.push(v);
                }
            }
        }
    }
}
void Steiner_Tree()
{
    int status = 1 << 8;
    for (int j = 0; j < status; j++)
    {
        for (int i = 1; i <= n; i++)
        {
            for (int k = j; k; k = (k - 1) & j)//集合划分
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[i][j - k]);
            if (dis[i][j] != inf)
            {
                que.push(i);
                used[i] = 1;
            }
        }
        spfa(j);
    }
}
bool vis[MAXM];
int ans[MAXM];
int main()
{
    ios::sync_with_stdio(0);
    cin >> n >> m;
    memset(dis, inf, sizeof(dis));
    memset(fir, -1, sizeof(fir));
    for (int i = 1; i <= n; i++)
    {
        string str;
        cin >> str;
        mp[str] = i;
    }
    for (int i = 1; i <= m; i++)
    {
        string stru, strv;
        int w;
        cin >> stru;
        cin >> strv;
        cin >> w;
        addedge(mp[stru], mp[strv], w);
        addedge(mp[strv], mp[stru], w);
    }
    for (int i = 1; i <= 8; i++)//对应状态 0-4 1-5 2-6 3-7
    {
        string str;
        cin >> str;
        int temp;
        if (i % 2)
            temp = i / 2;
        else
            temp = i / 2 + 3;
        dis[mp[str]][1 << temp] = 0;
    }
    int status = 1 << 8;
    Steiner_Tree();
    for (int j = 0; j < status; j++)
    {
        bool flag = 1;
        for (int i = 0; i < 4; i++)
        {
            if ((j >> i & 1) ^ (j >> (i + 4) & 1))
            {
                flag = 0;
                break;
            }
        }
        vis[j] = flag;
        ans[j] = inf;
        for (int i = 1; i <= n; i++)
            ans[j] = min(ans[j], dis[i][j]);
    }
    for (int j = 0; j < status; j++)
    {
        if (vis[j])
        {
            for (int i = j; i; i = (i - 1) & j)
            {
                if (vis[i] && vis[j - i])
                    ans[j] = min(ans[j], ans[i] + ans[j - i]);
            }
        }
    }
    printf("%d\n", ans[status - 1]);
    return 0;
}

发表留言

人生在世,错别字在所难免,无需纠正。