此题要注意松弛条件
#include<iostream> #include<queue> using namespace std; #define MAXSIZE 1000 typedef struct node{ int u; int v; double w; double c; }node; node p[MAXSIZE]; int head[MAXSIZE]; int next[MAXSIZE]; int n,m,s; double dis[MAXSIZE]; double v;//v 为初始拥有的货币数量 int e; queue<int>que; int vis[MAXSIZE]; int cnum[MAXSIZE]; int spfa(int s) { int i,j; while(!que.empty()) que.pop(); memset(vis,0,sizeof(vis)); memset(cnum,0,sizeof(cnum)); memset(dis,0,sizeof(dis));//初始时每个节点都没有钱 vis[s]=1; cnum[s]++; dis[s]=v; que.push(s); while(!que.empty())//当队列非空 { int te=que.front(); que.pop(); vis[te]=0; for(i=head[te];i!=-1;i=next[i])//取出te相连的所有点 { //if 利益增加了 则松弛(对应于 路径变短) //(现在拥有的货币-手续费)*比率 等于可以换得的货币 double tt=(dis[te]-p[i].c)*p[i].w;//dis[te] 表示te这个点拥有的资产 if(dis[p[i].v]<tt) { dis[p[i].v]=tt; if(!vis[p[i].v]) { vis[p[i].v]=1; cnum[p[i].v]++; que.push(p[i].v); if(cnum[p[i].v]>n) { return 1; } } } } } return 0; } void addnode(int u,int v,double w,double c) { p[e].u=u; p[e].v=v; p[e].w=w; p[e].c=c; next[e]=head[u]; head[u]=e++; } int main() { //freopen("in.txt","r",stdin); //while(scanf("%d%d%d%lf",&n,&m,&s,&v)!=EOF) { scanf("%d%d%d%lf",&n,&m,&s,&v); e=0; memset(head,-1,sizeof(head)); memset(next,-1,sizeof(next)); while(m--) { int a,b; double r1,c1,r2,c2; scanf("%d%d%lf%lf%lf%lf",&a,&b,&r1,&c1,&r2,&c2); addnode(a,b,r1,c1); addnode(b,a,r2,c2); } //spfa if(spfa(s)) printf("YES\n"); else printf("NO\n"); } }
相关推荐
北大POJ1789-Truck History【Prim】 解题报告+AC代码
北大POJ2002-Squares 解题报告+AC代码
北大POJ3253-POJ3253-Fence Repair【STL优先队列】 解题报告+AC代码
poj 1000 - 2000 部分题目 官方分类 poj 1000 - 2000 部分题目 官方分类
北大POJ1426-Find The Multiple【BFS+同余模】 解题报告+AC代码
北大POJ3020-Antenna Placement 解题报告+AC代码
这是魔兽世界终极版POJ的-测试数据,找了好久才找到的。 本来想设置为0积分,但是它居然自动收费(o_ _)ノ。 看传送门:https://pan.baidu.com/s/1cCIwW8psGDASu2JdZawG3Q
北大POJ3414-Pots 解题报告+AC代码
POJ3211--Washing Clothes
北大POJ2305-Basic remains POJ2305-Basic remains
北大POJ1321-Chess Problem POJ1321-Chess Problem
北大POJ1080-Human Gene Functions POJ1080-Human Gene Functions
POJ---1456.Supermarket测试数据及答案,题目描述:A supermarket has a set Prod of products on sale. It earns a profit px for each product x∈Prod sold by a deadline dx that is measured as an integral ...
POJ 1038--Bugs Integrated
POJ3036--Honeycomb Walk
poj 1000-3000部分代码 网上收集
北大POJ1159-Palindrome 解题报告+AC代码
北大POJ3273-Monthly Expense POJ3273-Monthly Expense
北大poj1012-Joseph【经典约瑟夫问题】 poj1012-Joseph【经典约瑟夫问题】
北大POJ2525-Text Formalization【TrieTree】 解题报告+AC代码+测试数据 http://hi.csdn.net/!s/XW4FQ3