POJ 3159 【朴素的差分约束】
2024-09-02 05:31:29
好吧终于知道什么是“高大上”的差分约束了。嗷嗷
题意:
小朋友们分糖果,某个小朋友不想另外一个小朋友分到的糖果数比自己多N块以上。
求编号为N的小朋友最多比编号为1的小朋友多分多少块糖果。
思路:
差分约束,用最短路做。
这题用SPFA.
查分约束的学习感谢博客:http://www.cnblogs.com/void/archive/2011/08/26/2153928.html
注意:
POJ也是拼,第一次碰到永std的queue会超时,需要手写一个人工栈的情况...
代码:
#include<stdio.h>
#include<algorithm>
#include<queue>
#include<string.h>
using namespace std;
const int inf=0x3f3f3f3f;
struct edge
{
int id,w;
edge *next;
};
edge edges[];
edge *adj[];
bool vis[];
int ednum;
int n,m;
int dis[];
void SPFA()
{
memset(vis,,sizeof(vis));
for(int i=;i<=n;i++)
{
dis[i]=inf;
}
dis[]=;
int q[];
int top=;
q[++top]=;
vis[]=;
while(top)
{
int tmp=q[top--];
vis[tmp]=;
for(edge *p=adj[tmp];p;p=p->next)
{
if(dis[p->id]>dis[tmp]+p->w)
{
dis[p->id]=dis[tmp]+p->w;
if(!vis[p->id])
{
q[++top]=p->id;
vis[p->id]=;
}
}
}
}
}
inline void addEdge(int a,int b,int c)
{
edge *tmp;
tmp=&edges[ednum];
ednum++;
tmp->id=b;
tmp->w=c;
tmp->next=adj[a];
adj[a]=tmp;
}
int main()
{
int a,b,c;
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++)
{
scanf("%d%d%d",&a,&b,&c);
addEdge(a,b,c);
}
SPFA();
printf("%d\n",dis[n]);
}
最新文章
- ios使用jspatch中需要注意的事项
- 前端HTML-CSS规范
- could not deduce template argument for &#39;const std::_Tree<;_Traits>; &;&#39; from &#39;const std::string&#39;
- hdu, KMP algorithm, linear string search algorithm, a nice reference provided 分类: hdoj 2015-07-18 13:40 144人阅读 评论(0) 收藏
- hdu 1024 Max Sum Plus Plus
- window8家庭版上的RationalRose
- Linux中的MyEclipse配置Hadoop
- 部分视图调用方法总结(Action 、 RenderAction 、 Partial 、 RenderPartial)
- 谈B2B电商平台与大数据
- Android Studio下载安装及配置图文教程
- 分享非常有用的Java程序 (关键代码) (三)---创建ZIP和JAR文件
- minihomepage.exe 百度视频迷你主页
- Shuttle ESB(四)——宣布订阅模式实例介绍(1)
- checkbox/input文本框与文字对齐
- BZOJ_3316_JC loves Mkk_ 二分答案 + 单调队列
- git创建分支并提交到远程分支
- keras使用
- Mock.js简易教程,脱离后端独立开发,实现增删改查功能(转)
- Food HDU - 4292 (结点容量 拆点) Dinic
- 为什么说 HashMap 是非线程安全的?