hdu4085 Peach Blossom Spring 斯坦纳树，状态dp

 

（2）注意dp[i][ss] = min(dp[i][ss], dp[i][rr | s[i]] + dp[i][(ss ^ rr) | s[i]]);，后面的要 |s[i],保证状态的正确

 

（3）INF初始化CLR（dp， 0x3f）

 

（4）注意斯坦纳树状态理解，分层松弛的理解

 

参考：http://endlesscount.blog.163.com/blog/static/821197872012525113427573/

 

//#pragma warning (disable: 4786)  
//#pragma comment (linker, "/STACK:16777216")  
//HEAD  
#include <cstdio>  
#include <ctime>  
#include <cstdlib>  
#include <cstring>  
#include <queue>  
#include <string>  
#include <set>  
#include <stack>  
#include <map>  
#include <cmath>  
#include <vector>  
#include <iostream>  
#include <algorithm>  
using namespace std;  
//LOOP  
#define FE(i, a, b) for(int i = (a); i <= (b); ++i)  
#define FED(i, b, a) for(int i = (b); i>= (a); --i)  
#define REP(i, N) for(int i = 0; i < (N); ++i)  
#define CLR(A,value) memset(A,value,sizeof(A))  
//INPUT  
#define RI(n) scanf("%d", &n)  
#define RII(n, m) scanf("%d%d", &n, &m)  
#define RIII(n, m, k) scanf("%d%d%d", &n, &m, &k)  
#define RS(s) scanf("%s", s)  
  
typedef long long LL;  
const int INF = 0x3f3f3f3f;  
const double eps = 1e-10;  
const int MAXN = 1000010;  
  
struct node{  
    int to, next, l;  
};  
int tol;  
node adj[2010];  
int head[55];  
void init_adj()  
{  
    tol = 0;  
    CLR(head, -1);  
}  
void add_edge(int x, int y, int ll)  
{  
    adj[tol].to = y;  
    adj[tol].l = ll;  
    adj[tol].next = head[x];  
    head[x] = tol++;  
}  
int dp[55][1 << 11];  
queue<int>q;  
bool inq[55][1 << 11];  
int d[1 << 11];  
int s[55];  
int n, m, k;  
int cnt, ALL;  
  
bool check(int ss)  
{  
    int num = 0;  
    for (int i = 0; i < cnt; i++)  
        if (ss & (1 << i))  
            num += i < k ? 1 : -1;  
    if (!num) return 1;  
    return 0;  
}  
  
void spfa()  
{  
    while (!q.empty())  
    {  
        int u = q.front(); q.pop();  
        int ui = u / 10000;  
        int uss = u % 10000;  
        inq[ui][uss] = 0;  
        for (int r = head[ui]; r != -1; r = adj[r].next)  
        {  
            int vi = adj[r].to;  
            int vss = uss | s[vi];  
            if (dp[vi][vss] > dp[ui][uss] + adj[r].l)  
            {  
                dp[vi][vss] = dp[ui][uss] + adj[r].l;  
                if (vss == uss && !inq[vi][vss]) /// 同层且不再队列中  
                {  
                    inq[vi][vss] = 1;  
                    q.push(vi * 10000 + vss);  
                }  
            }  
        }  
    }  
}  
  
void solve()  
{  
    while (!q.empty()) q.pop();  
    CLR(inq, 0);  
    FE(ss, 0, ALL)  
    {  
        FE(i, 1, n)  
        {  
            for (int rr = ss & (ss - 1); rr; rr = (rr - 1) & ss)///ss  
                    dp[i][ss] = min(dp[i][ss], dp[i][rr | s[i]] + dp[i][(ss ^ rr) | s[i]]);  
            if (dp[i][ss] < INF)  
                q.push(i * 10000 + ss), inq[i][ss] = 1;  
        }  
        spfa();  
    }  
  
    CLR(d, 0x3f);  
    FE(ss, 0, ALL) FE(j, 1, n)  
        d[ss] = min(d[ss], dp[j][ss]);  
  
    REP(ss, ALL + 1)  
        for(int rr = ss & (ss - 1); rr; rr = (rr - 1) & ss)  
            if (check(rr) && check(ss ^ rr))  
                d[ss] = min(d[ss], d[rr] + d[ss ^ rr]);  
  
    if (d[ALL] == INF) printf("No solution\n");  
    else printf("%d\n", d[ALL]);  
}  
  
  
void init()  
{  
    int x, y, l;  
    init_adj();  
    RIII(n, m, k);  
    while (m--)  
    {  
        RIII(x, y, l);  
        add_edge(x, y, l);  
        add_edge(y, x, l);  
    }  
  
    cnt = 2 * k;  
    ALL = (1 << cnt) - 1;  
  
    CLR(s, 0);  
    CLR(dp, 0x3f);  
  
    FE(i, 1, k)///集合  
    {  
        s[i] = 1 << (i - 1);  
        dp[i][s[i]] = 0;  
        s[n - k + i] = 1 << (k + i - 1);  
        dp[n - k + i][s[n - k + i]] = 0;  
    }  
}  
  
int main ()  
{  
    int T;  
    RI(T);  
    while (T--)  
    {  
        init();  
        solve();  
    }  
    return 0;  
}  

 

 

补充：软件开发 , C++ ,