分析：运用两次spfa，求出每个城市最大卖出价格和最小买入价格差值，求个最大值就ok了。
#include<fstream>
#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
const int N(100008);
struct node
{
int adj;
node *next;
};
node *g1[N]={0},*g2[N]={0};
int n,m,buy[N],sell[N],price[N];
bool inq[N];
queue<int> q;
void init()
{
int x,y,z;
node *p;
for (int i=0;i<m;i++)
{
scanf("%d%d%d",&x,&y,&z);
p=new(node); p->adj=y; p->next=g1[x]; g1[x]=p;
p=new(node); p->adj=x; p->next=g2[y]; g2[y]=p;
if (z==2)
{
p=new(node); p->adj=x; p->next=g1[y]; g1[y]=p;
p=new(node); p->adj=y; p->next=g2[x]; g2[x]=p;
}
}
}
void spfa1() //求最小买入价格
{
int k;
node *p;
fill(buy+1,buy+n+1,0x7fffffff);
fill(inq+1,inq+n+1,0);
buy[1]=price[1];
q.push(1);
inq[1]=true;
while (!q.empty())
{
k=q.front();
q.pop();
inq[k]=false;
p=g1[k];
while (p)
{
if (min(price[p->adj],buy[k])<buy[p->adj])
{
buy[p->adj]=min(price[p->adj],buy[k]);
if (!inq[p->adj])
{
q.push(p->adj);
inq[p->adj]=true;
}
}
p=p->next;
}
}
}
void spfa2() //求最大卖出价格
{
int k;
node *p;
fill(sell+1,sell+n+1,0);
fill(inq+1,inq+n+1,0);
sell[n]=price[n];
q.push(n);
inq[n]=true;
while (!q.empty())
{
k=q.front();
q.pop();
p=g2[k];
while (p)
{
if (max(price[p->adj],sell[k])>sell[p->adj])
{
sell[p->adj]=max(price[p->adj],sell[k]);
if (!inq[p->adj])
{
q.push(p->adj);
inq[p->adj]=true;
}
}
p=p->next;
}
}
}
int main()
{
freopen("trade.in","r",stdin);
freopen("trade.out","w",stdout);
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++) scanf("%d",&price[i]);
init();
spfa1();
spfa2();
int ans(0);
for (int i=1;i<=n;i++)
if (sell[i]-buy[i]>ans) ans=sell[i]-buy[i];
printf("%d\n",ans);
return 0;
}
posted on 2013-01-14 11:55
龙在江湖 阅读(442)
评论(0) 编辑 收藏 引用 所属分类:
图论 、
竞赛题解_NOIP