首页 > 代码库 > ZOJ 2770 Burn the Linked Camp
ZOJ 2770 Burn the Linked Camp
差分约束(最短路)
不等式用最短路来求。问题是好难找约束条件——建立不等式。
题意问最少有多少兵。即建立好各点的约束条件,求0~N 的最短路。
有负环得判断入队次数。
反正还没多大理解差分约束,Hurry up!
#include<cstdio> #include<cstring> #include<string> #include<queue> #include<algorithm> #include<map> #include<stack> #include<iostream> #include<list> #include<set> #include<cmath> #define INF 0x7fffffff #define eps 1e-6 #define LL long long using namespace std; int n,m; int d[1001]; struct lx { int v,len; }; vector <lx> g[1001]; int SPFA() { queue<int>q; int dis[1001]; bool vis[1001]; int que[1001]; for(int i=0;i<=n;i++) dis[i]=INF,que[i]=vis[i]=0; q.push(0); vis[0]=1,dis[0]=0; while(!q.empty()) { int u=q.front();q.pop(); vis[u]=0,que[u]++; if(que[u]>n)return 1; for(int j=0;j<g[u].size();j++) { int v=g[u][j].v; int len=g[u][j].len; if(dis[v]>dis[u]+len) { dis[v]=dis[u]+len; if(!vis[v]) { vis[v]=1; q.push(v); } } } } return dis[n]; } int main() { while(scanf("%d%d",&n,&m)!=EOF) { int u,v,len; for(int i=0;i<=n;i++) g[i].clear(); d[0]=0; lx now; for(int i=1; i<=n; i++) { scanf("%d",&d[i]); now.v=i-1,now.len=d[i]; g[i].push_back(now); now.v=i,now.len=0; g[i-1].push_back(now); d[i]=d[i-1]+d[i]; } while(m--) { scanf("%d%d%d",&u,&v,&len); now.v=v,now.len=-len; g[u-1].push_back(now); now.v=u-1,now.len=d[v]-d[u-1]; g[v].push_back(now); } // for(int i=0;i<=n;i++) // { // printf("%d -> ",i); // for(int j=0;j<g[i].size();j++) // printf("%d:%d ",g[i][j].v,g[i][j].len); // printf("\n"); // } int tmp=SPFA(); if(tmp==1) puts("Bad Estimations"); else printf("%d\n",-tmp); } }
ZOJ 2770 Burn the Linked Camp
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。