【并查集+贪心(或)最短路+二分枚举】HDU 1598

http://acm.hdu.edu.cn/showproblem.php?pid=1598

题意：找到从起点到终点的一条路，而且这条路经过的边的最大权值与最小权值之差最小，输出这个差

①最短路+二分枚举
二分枚举差，再枚举下界，上界=下界+差，在上下界的限制之下仍可到达终点，说明存在这么一个差，但是差还可能更小，所以继续二分

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
#define inf 0x3fffffff
#define M 205					//最大点数

struct son{
    int v, w;
};
vector<son> g[M];
bool inq[M];					//入队列标记
int dist[M], tp[1005], n;		//n：实际点数

void init ()
{
	for (int i = 1; i <= n; i++)
		g[i].clear();
}

bool spfa (int u, int low, int high, int t)
{
    int i, v, w;
    for (i = 1; i <= n; i++)
    {
        dist[i] = inf;
        inq[i] = false;
    }
    queue<int> q;
    q.push (u);
    inq[u] = true;
    dist[u] = 0;
    while (!q.empty())
    {
        u = q.front();
        q.pop();
        inq[u] = false;
        for (i = 0; i < g[u].size(); i++)
        {
            v = g[u][i].v;
            w = g[u][i].w;
			if (w < low || w > high)	//限制条件
				continue;
            if (dist[u] + w < dist[v])
            {
				if (v == t)				//可以到达终点返回true
					return true;
                dist[v] = dist[u] + w;
                if (!inq[v])
                {
                    q.push (v);
                    inq[v] = true;
                }
            }
        }
    }
	return false;
}

int main()
{
	bool flag;
	int m, u, v, i, l, r, mid, maxs;
	son x;
	while (~scanf ("%d%d", &n, &m))
	{
		init();
		maxs = 0;
		for (i = 0; i < m; i++)
		{
			scanf ("%d%d%d", &u, &v, tp+i);
			if (maxs < tp[i])
				maxs = tp[i];
			x.v = v, x.w = tp[i];
			g[u].push_back (x);
			x.v = u;
			g[v].push_back (x);
		}
		sort (tp, tp+m);	//边的权值从小到大排序
		int q;
		scanf ("%d", &q);
		while (q--)
		{
			scanf ("%d%d", &u, &v);
			l = 0, r = maxs;
			int ans = -1;
			while (l <= r)	//二分枚举舒适度差
			{
				flag = false;
				mid = (l+r) >> 1;	//mid就是差
				for (i = 0; tp[i] + mid <= maxs; i++)
				{
					if (spfa (u, tp[i], tp[i]+mid, v))
					{
						flag = true;
						break;
					}
				}
				if (flag)
					ans = mid, r = mid - 1;
				else l = mid + 1;
			}
			printf ("%d\n", ans);
		}
	}
    return 0;
}

②并查集+贪心
枚举最小边，再从小到大一直加大于等于这个最小边的其他边，直到起点跟终点属于同一个集合为止，然后用最大边-最小边的差，看能不能更新mins【结果】

#include <iostream>
#include <algorithm>
using namespace std;
#define inf 0x3fffffff
#define M 205

struct edge{
    int a, b;
    int w;
}e[1005];
int pre[M], n;

int find (int a)
{
    while (a != pre[a])
        a = pre[a];
    return a;
}

void init ()
{
    for (int i = 1; i <= n; i++)
        pre[i] = i;
}

bool cmp (edge x, edge y)
{
    return x.w < y.w;
}

int main()
{
    int m, i, a, b, q, A, B, j, mins;
    while (~scanf ("%d%d", &n, &m))
    {
        for (i = 0; i < m; i++)
            scanf ("%d%d%d", &e[i].a, &e[i].b, &e[i].w);
        sort (e, e+m, cmp);			//边集按权值从小到大排序
        scanf ("%d", &q);
        while (q--)
        {
            scanf ("%d%d", &a, &b);
            mins = inf;
            for (i = 0; i < m; i++)		//枚举最小边
            {
                init();
                for (j = i; j < m; j++)    //寻找最大边
                {
                    A = find (e[j].a);
                    B = find (e[j].b);
                    if (A != B)
                        pre[B] = A;
                    if (find(a) == find(b))//并查集把起点和终点连接起来了就更新mins
                    {	//因为有序，所以连接ab的边权值最小为e[i].w，最大为e[j].w
                        if (mins > e[j].w - e[i].w)
                            mins = e[j].w - e[i].w;
                        break;
                    }
                }
                if (j == m)			//j==m 则继续枚举也不可能令find(a) == find(b)
                    break;
            }
            if (mins == inf)
                puts ("-1");
            else printf ("%d\n", mins);
        }
    }
    return 0;
}

评论

1 楼 nuptxxp 2012-01-11  

写的很好~