POJ 3159 Candies(差分约束)
http://poj.org/problem?id=3159
题意:幼儿园有n个小朋友分糖果,现在有m个如下形式的条件需要满足: a b c 表示b同学糖果数-a同学糖果数<=c. 现在问你满足m个条件的情况下,要使得n号同学糖果数-1号同学糖果数的差值最大为多少?
分析:
第一道差分约束题…
首先对于m个条件来说,如果b-a<=c,那么从a到b有一条长c的边.现在我们要求的是d[n]与d[1]的差距最大,所以初始化应该令d[1]=0,且d[i]=INF( i>0). (根据百度百科对差分约束的介绍)
又由于该题中的c值都是正数,所以不会存在负权路或环.所以直接Dijkstra求1号点到其他所有点的最短距离即可得到解:d[n]-d[1].
根据算法导论的讲解,其实差分约束本来就是用最短路求解的.不过存在负权环的情况,所以用BellmanFord算法还可以判断出无解的情况.
AC代码:
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define INF 1e9
using namespace std;
const int maxn=30000+10;
const int maxm=150000+10;
struct Edge
{
int from,to,dist;
Edge(){}
Edge(int f,int t,int d):from(f),to(t),dist(d){}
};
struct HeapNode
{
int d,u;
HeapNode(int d,int u):d(d),u(u){}
bool operator<(const HeapNode &rhs)const
{
return d>rhs.d;
}
};
struct Dijkstra
{
int n,m;
int head[maxn],next[maxm];
Edge edges[maxm];
int d[maxn];
bool done[maxn];
void init(int n)
{
this->n=n;
m=0;
memset(head,-1,sizeof(head));
}
void AddEdge(int from,int to,int dist)
{
edges[m]=Edge(from,to,dist);
next[m]=head[from];
head[from]=m++;
}
int dijkstra()
{
priority_queue<HeapNode> Q;
for(int i=0;i<n;i++) d[i]= i==0?0:INF;
memset(done,0,sizeof(done));
Q.push(HeapNode(d[0],0));
while(!Q.empty())
{
HeapNode x=Q.top(); Q.pop();
int u=x.u;
if(done[u]) continue;
done[u]=true;
for(int i=head[u];i!=-1;i=next[i])
{
Edge &e=edges[i];
if(d[e.to]>d[u]+e.dist)
{
d[e.to]= d[u]+e.dist;
Q.push(HeapNode(d[e.to],e.to));
}
}
}
return d[n-1];
}
}DJ;
int main()
{
int n,m;
scanf("%d%d",&n,&m);
DJ.init(n);
while(m--)
{
int u,v,d;
scanf("%d%d%d",&u,&v,&d);
u--,v--;
DJ.AddEdge(u,v,d);
}
printf("%d\n",DJ.dijkstra());
return 0;
}
分享到:
相关推荐
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
北大POJ2983-Is the Information Reliable【差分约束+优化Bellman】 解题报告+AC代码
poj分类poj分类poj分类poj分类
poj 百练 题目分类 poj 百练 题目分类
POJ题目分类POJ题目分类POJ题目分类
POJ题解及题目分类,共150道左右。C/C++
该文档对poj大部分题目进行了分类,有利于喜欢在poj刷题的朋友
poj上的算法题目分类,对于大家想练习算法的同鞋可以参考一下,里面按类列出了各种算法的题号。
pojACM题目分类,便于各类型同学分别做题有所参考
poj800多道题目的详细分类,比较具体,比网上的好多了值得下载。
poj题目分类
POJ题目分类,列出了所有的类目,里面写了一些很好的框架。
poj题目分类打包 acm北大的题库题目分类 来源网络 网络还有自己整理一部分。好久前的玩意了
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
强大的poj分类 学做POJ必备 非最新,供参考
史上最全poj题目分类及原题 包括:基本算法:贪心、递归、递推、枚举;基本数据结构,链表、栈;动态规划;搜索;高级数据结构:二叉搜索树、线段树、树状数组;数学:数论
史上最全poj题目分类(159页).pdf
这是关于 ACM程序设计 POj系统 题目的 一些题目分类的 希望对大家有用!
关于poj dp分类,我一直寻找dp的分类,终于找到了,也上传一下
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码