`

【并查集+贪心(或)最短路+二分枚举】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;
}
2
2
分享到:
评论
1 楼 nuptxxp 2012-01-11  
写的很好~

相关推荐

    (HDUACM201403版_06)并查集(最小生成树)

    杭电ACM课件2014版之 (HDUACM201403版_06)并查集(最小生成树)

    (HDUACM2010版_06)并查集(最小生成树)

    (HDUACM2010版_06)并查集(最小生成树(HDUACM2010版_06)并查集(最小生成树(HDUACM2010版_06)并查集(最小生成树(HDUACM2010版_06)并查集(最小生成树

    acm入门之枚举搜索

    acm入门之枚举搜索,学校第一次acm培训,包括枚举及其优化,dfs和bfs

    并查集问题

    3. (HDUACM2010版_06)并查集(最小生成树).ppt:这是一个PPT文件,可能详细介绍了如何使用并查集来求解最小生成树的问题,包括理论知识、算法流程和示例解析。 4. hdoj1829二分图识别的并查集.txt:二分图是图论...

    ACM HDU题目分类

    ACM HDU 题目分类 ACM HDU 题目分类是指对 HDU 在线判题系统中题目的分类,总结了大约十来个分类。这些分类将有助于编程选手更好地理解和解决问题。 DP 问题 DP(Dynamic Programming,动态规划)是一种非常重要...

    最短路(HDU-2544).rar

    1. Dijkstra算法:Dijkstra算法是最常用且基础的单源最短路算法,它使用贪心策略,逐步扩展从源节点s出发的最短路径树。算法保证了每次扩展的都是当前未访问节点中距离源节点最近的一个,最终得到s到所有节点的最短...

    二分匹配题集

    - **知识点**:最短路+二分匹配问题。 - **解题思路**:构建二分图模型,使用二分法优化最大匹配算法,同时结合最短路算法求解。 33. **Adopt or not (HDU 3517)** - **知识点**:最大独立集问题。 - **解题...

    HDU 6187 Destroy Walls(并查集)

    使用并查集+贪心:先将已有边的权值从大到小排序,又n个点只需n-1条边,这时再遍历一遍,将有边的两点合并为一个队伍,当边的数量达到n-1时退出循环,因为此时已达到最小生成树。 边的权值由大到小排序是因为要将大...

    acm课件 HDU 算法大全

    acm 技术大牛 课件 HDU 自学必备课件 全套齐全 (lecture_01)初识ACM (lecture_02)简单数学题 (lecture_03)递推求解 (lecture_04)动态规划(1)_ (lecture_05)计算几何基础_ (lecture_06)母函数 ...并查集

    hdu.rar_hdu

    1. **基础算法**:如排序(冒泡、选择、插入、快速、归并等)、搜索(线性、二分、深度优先、广度优先等)。 2. **高级算法**:包括动态规划(状态转移、记忆化搜索)、贪心策略、回溯法、分支限界法等。 3. **...

    HDU-ACM课件.rar

    8. **并查集**:并查集是一种用于处理集合合并和查询是否属于同一集合的数据结构。在图论中,它可以用来判断两个节点是否连通,常用于求解连通性问题,如判定树是否为森林或求得强连通分量。 9. **母函数**:在数论...

    HDU+2000-2099+解题报告.zip

    4. **排序与搜索**:快速排序、归并排序、二分查找等经典算法在HDU题目中经常出现。解题报告会深入讲解这些算法的原理和应用场景,并给出高效的实现代码。 5. **字符串处理**:包括KMP算法、Manacher's Algorithm等...

    (HDUACM2010版_13)二分匹配及其应用

    杭电ACM课件2014版之(HDUACM2010版_13)二分匹配及其应用

    hdu题目分类

    贪心算法是在每一步选择中都采取在当前状态下最好或最优(即最有利)的选择策略,以便产生全局最优解的算法。例如,题目1009、1045等,贪心算法要求选手能够识别出局部最优解与全局最优解的关系,通过一系列的局部...

    HDU二分匹配及其应用

    HDU二分匹配及其应用,此PPT是刘春英老师版权所有, 特此贡献给广大编程爱好者,特别是对于ACMer

    hdu ACM代码 每种算法都有分类

    6. **数据结构**:线段树、斐波那契堆、平衡树(AVL、红黑树)、字典树(Trie)、并查集等,这些高级数据结构可以高效地解决区间查询、维护、集合操作等问题。 7. **几何算法**:二维和三维几何问题,如点线面的...

Global site tag (gtag.js) - Google Analytics