差分約束系統。
以下是我的代碼：
/*
* Author: lee1r
* Created Time: 2011/8/2 19:46:45
* File Name: zoj2770.cpp
*/
#include<iostream>
#include<sstream>
#include<fstream>
#include<vector>
#include<list>
#include<deque>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<cmath>
#include<ctime>
#define L(x) ((x)<<1)
#define R(x) (((x)<<1)+1)
#define Half(x) ((x)>>1)
#define lowbit(x) ((x)&(-(x)))
using namespace std;
const long long kInf(0x7f7f7f7f7f7f7f7fll);
const double kEps(1e-11);
typedef long long int64;
typedef unsigned long long uint64;
const int kMaxn(1007);
const int kMaxm(20007);
struct Edge
{
int u,v,w;
};
int n,m,cnt;
Edge e[kMaxm];
int64 ans;
void AddEdge(int u,int v,int w)
{
cnt++;
e[cnt].u=u;
e[cnt].v=v;
e[cnt].w=w;
}
int64 BellmanFord()
{
int64 d[kMaxn];
d[n]=0;
for(int i=0;i<n;i++)
d[i]=kInf;
for(int i=0;i<n;i++)
for(int j=1;j<=cnt;j++)
if(d[e[j].u]<kInf && d[e[j].v]>d[e[j].u]+e[j].w)
d[e[j].v]=d[e[j].u]+e[j].w;
for(int i=1;i<=cnt;i++)
if(d[e[i].v]>d[e[i].u]+e[i].w)
return -1;
return d[0];
}
int main()
{
while(scanf("%d%d",&n,&m)==2)
{
cnt=0;
for(int i=1;i<=n;i++)
{
int t;
scanf("%d",&t);
AddEdge(i-1,i,t);
AddEdge(i,i-1,0);
}
for(int i=1;i<=m;i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
AddEdge(v,u-1,-w);
}
ans=BellmanFord();
if(ans==-1)
printf("Bad Estimations\n");
else
cout<<-ans<<endl;
}
return 0;
}
posted on 2011-08-02 20:19
lee1r 閱讀(329)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：圖論