大致题意:
给n个小孩发糖吃,给出m组约束条件,每组条件包含三个数字a b c,表示b得到的糖果数目不能比a多超过c个。求第n个人得到的糖果数比第一个人最多能多几个。
大致思路:
spfa差分约束,dis[i]为第i人得到的糖果数目。对于每个约束管理就能列出不等式:dis[a]>=dis[b]-c,就能转化为dis[b]<=dis[a]+c。也就是差分约束最短路中的三角不等式。又由于这里求的是第n点与第1个点的关系,所以就把1设为最短路中的其实点而不舍虚拟起始点。按照这个关系建出图求出最短路,则dis[n]就是答案。
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
using namespace std;
const int nMax=105000;
const int mMax=10000500;
const int inf=1<<28;
struct{
int v, next;
int w;
}edge[mMax];
int n, k, head[nMax];
int dis[nMax];
int stack[nMax],m,sum[nMax];
bool vis[nMax];
void addedge(int a,int b,int w){
edge[k].w = w;
edge[k].v=b;
edge[k].next=head[a];
head[a]=k;k++;
}
bool spfa(int s){
int i, top = 0;
memset(vis,0,sizeof(vis));
for(i=0;i<=n;i++)dis[i]=inf;
dis[s]=0;
stack[++top]=s;
vis[s]=true;
while(top){
int u=stack[top--];
for(i=head[u];i!=0;i=edge[i].next){
int v=edge[i].v;
if(dis[v]>dis[u]+edge[i].w){
dis[v]=dis[u]+edge[i].w;
if(!vis[v]){
vis[v]=true;
stack[++top] = v;
if(++sum[v]>n)return 0;
}
}
}
vis[u]=false;
}
return 1;
}
int main(){
int m,i,j,a,b,c,s;
while(scanf("%d%d",&n,&m)!=EOF){
k=1;
s=1;
memset(head,0,sizeof(head));
while(m--){
scanf("%d%d%d",&a,&b,&c);
addedge(a,b,c);
}
spfa(s);
cout<<dis[n]<<endl;
}
return 0;
}
分享到:
相关推荐
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
NULL 博文链接:https://128kj.iteye.com/blog/1754756
北大POJ2983-Is the Information Reliable【差分约束+优化Bellman】 解题报告+AC代码
这是西北工业大学的POJ试题的答案,欢迎下载!
网上整理的一些poj刷题指南。 poj地址:http://poj.org
poj分类poj分类poj分类poj分类
POJ题目分类POJ题目分类POJ题目分类
poj 百练 题目分类 poj 百练 题目分类
该文档对poj大部分题目进行了分类,有利于喜欢在poj刷题的朋友
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
poj题目分类
史上最全poj题目分类及原题 包括:基本算法:贪心、递归、递推、枚举;基本数据结构,链表、栈;动态规划;搜索;高级数据结构:二叉搜索树、线段树、树状数组;数学:数论
强大的poj分类 学做POJ必备 非最新,供参考
pojACM题目分类,便于各类型同学分别做题有所参考
twilight-poj-solutionPOJ () solution by twilight想当年要找一题的分析, 解答实在太难了现在都是开源的时代了, 干脆把Archive放到GitHub上, 供后来人参考.POJ ID: 部分题解: 转载请注明出处~
poj 算法题在poj.org上做的一些算法题poj.org 账号:xxfeixiang题目地址:例如,第1001题的地址为:
史上最全poj题目分类(159页).pdf
poj题目分类打包 acm北大的题库题目分类 来源网络 网络还有自己整理一部分。好久前的玩意了
POJ题目分类,列出了所有的类目,里面写了一些很好的框架。
POJ 3267 POJ 1260 POJ 1015 POJ 3176 POJ 1080 POJ 1159 POJ 2533 POJ 1836 Leetcode 70 Leetcode 309 搜索 DFS POJ 2488 POJ 3083 POJ 3009 POJ 1321 BFS POJ 3278 POJ 1426 POJ 3126 POJ 3414 POJ 2251 简单搜索...