之前本沙茶成功地在网络流图中搞出Dancing Link边表,那么对于一般的图,是否也能用Dancing Link边表呢?答案是肯定的。

边类型(带权的,不带边权的图把len域去掉即可):
struct edge {
    
int a, b, len, pre, next;
} ed[MAXM];
初始化表头:
void init_d()
{
    re(i, n) ed[i].a 
= ed[i].pre = ed[i].next = i;
    
if (n % 2) m = n + 1else m = n;
}
加边(这里是加有向边,如果加无向边的话,再加一条边<b, a, len>即可):
void add_edge(int a, int b, int len)
{
    ed[m].a 
= a; ed[m].b = b; ed[m].len = len; ed[m].pre = ed[a].pre; ed[m].next = a; ed[a].pre = m; ed[ed[m].pre].next = m++;
}
在一般的图中应用Dancing Link边表的优势:【1】能够有效处理删边删点问题;【2】在无向图中,能够很快找到一条边对应的逆向边;【3】最大的优势是:如果要从某一条单点链表(其实整个边表可以看成N个单点链表的并,N为图中的点数)的中间开始遍历,或者逆向遍历整个表的话,一般的邻接链表几乎不可能完成,一般的边表也很麻烦,这种Dancing Link边表则可以很快搞定。不过它也有缺点:空间消耗比邻接链表和一般边表大一些(不过这个影响不大)。

【应用实例】PKU1062(PKU上少有的中文题)
很水的最短路问题。将每个物品当成一个点,若j可作为i的优惠品则连边<i, j>,边权为优惠价格,然后,枚举等级限制(由于物品1是必须选的,因此设最大等级限制为lmt,物品1的等级为V,则可在[V-lmt, V]范围内枚举最低等级,最高等级就是(最低等级+lmt)),将所有不在等级限制内的点全部删除(其实不用真删除,只要设一个del数组避开它们即可),求从结点1到各结点的最短路,则min(dist[i]+cs[i])(dist[i]表示1到i的最短路,cs[i]表示直接购买物品i的价格)就是结果。
代码(2Y,一开始把solve里的g[j]弄成g[i]了囧……静态查错V5啊……神犇不要鄙视):
#include <iostream>
#include 
<stdio.h>
#include 
<queue>
#include 
<utility>
using namespace std;
#define re(i, n) for (int i=0; i<n; i++)
#define re3(i, l, r) for (int i=l; i<=r; i++)
typedef pair 
<intint> i_i;
typedef priority_queue 
<i_i, vector<i_i>, greater<i_i> > pqi_i;
const int MAXN = 100, MAXM = 30000, INF = ~0U >> 2;
struct edge {
    
int a, b, len, pre, next;
} ed[MAXM];
int n, m, s, lmt, cs[MAXN], g[MAXN], dist[MAXN], res = INF;
bool del[MAXN];
pqi_i q;
void init_d()
{
    re(i, n) ed[i].a 
= ed[i].pre = ed[i].next = i;
    
if (n % 2) m = n + 1else m = n;
}
void add_edge(int a, int b, int len)
{
    ed[m].a 
= a; ed[m].b = b; ed[m].len = len; ed[m].pre = ed[a].pre; ed[m].next = a; ed[a].pre = m; ed[ed[m].pre].next = m++;
}
void init()
{
    
int b0, x, y;
    scanf(
"%d%d"&lmt, &n);
    init_d();
    re(i, n) {
        scanf(
"%d%d%d"&cs[i], &g[i], &x);
        re(j, x) {
            scanf(
"%d%d"&b0, &y);
            add_edge(i, 
--b0, y);
        }
    }
}
void sol1()
{
    re(i, n) 
if (!del[i]) dist[i] = INF + 1; q.push(i_i(0, s));
    
int i, j, d0, d1;
    
while (!q.empty()) {
        d0 
= q.top().first; i = q.top().second; q.pop();
        
if (dist[i] == INF + 1) {
            dist[i] 
= d0;
            
for (int p=ed[i].next; p != i; p=ed[p].next) {
                j 
= ed[p].b;
                
if (!del[j]) {
                    d1 
= d0 + ed[p].len; q.push(i_i(d1, j));
                }
            }
        }
    }
    re(i, n) 
if (!del[i]) {
        d0 
= cs[i] + dist[i];
        
if (d0 < res) res = d0;
    }
}
void solve()
{
    
int lf, rt; s = 0;
    re3(i, 
0, lmt) {
        lf 
= g[s] - i; rt = lf + lmt;
        re(j, n) del[j] 
= g[j] < lf || g[j] > rt;
        sol1();
    }
}
void pri()
{
    printf(
"%d\n", res);
}
int main()
{
    init();
    solve();
    pri();
    
return 0;
}

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理