锐客网

  1. 首页 > it技术 > >

POJ2240 spfa判增大环 poj3259 spfa判负环

最短路

poj2240 题目：
想利用美元套利，就是100美元->50英镑->500发廊->105美元
问有没有这种路径能利用美元套利
思路:
①map处理
②spfa判正环，咦？spfa不是判负环吗，怎么判正环啊，也是个思维哦！
③一些写法，也可以用链式前向星，我用的vector邻接表，因为这个题最大N为30，只要写对，不用关心算复杂度了

#include #include #include #include #include #include #include #include #include #include #include using namespace std; int n,m; queue cun; typedef pair pid; map,int> si; vector tu[50]; vector::iterator it; double dis[50]; int vis[50]; int spfa() { while(!cun.empty()) cun.pop(); memset(vis,0,sizeof(vis)); memset(dis,0,sizeof(dis)); //zhege???? dis[1]=1.0; cun.push(1); vis[1]=1; while(!cun.empty()) { int t=cun.front(); cun.pop(); vis[t]=0; for(it=tu[t].begin(); it!=tu[t].end(); it++) { int v=it->first; double w=it->second; if(dis[v]1) { return 1; } } if(dis[1]>1) { return 1; } return 0; }int main() { int ttt=1; string a,b; int u,v; while(scanf("%d",&n)!=EOF&&n) {string str; si.clear(); for(int i=1; i<=n; i++) { cin>>str; tu[i].clear(); si[str]=i; }cin>>m; double zhi; for(int j=0; j>a>>zhi>>b; u=si[a]; v=si[b]; tu[u].push_back({v,zhi}); } cout<<"Case "<

poj3259 【POJ2240 spfa判增大环 poj3259 spfa判负环】题意：一个农场有m条无向边，每边花费时间C x条单向虫洞，每次进入虫洞，返回时间C然后到另一结点
问能不能见到过去的自己；
思路：判负环问题，如果一个点能优化n次以上，就说明有负环。
#include #include #include #include #include #include #include #include #include #include #include using namespace std; int x,y; int n,m; queue cun; typedef pair pii; vector tu[505]; vector::iterator it; int dis[505],vis[505]; int cnt[505]; int spfa(){ while(!cun.empty())cun.pop(); memset(vis,0,sizeof(vis)); memset(cnt,0,sizeof(cnt)); memset(dis,0x3f,sizeof(dis)); cun.push(1); vis[1]=1; dis[1]=0; while(!cun.empty()){ int tmp=cun.front(); cun.pop(); cnt[tmp]++; if(cnt[tmp]>n){ return -1; } vis[tmp]=0; for(it=tu[tmp].begin(); it!=tu[tmp].end(); it++){ int w=it->second; int v=it->first; if(dis[v]>dis[tmp]+w){ dis[v]=dis[tmp]+w; if(!vis[v]){cun.push(v); vis[v]=1; } } }}return 0; } int main() { int t; int a,b,c; scanf("%d",&t); while(t--){ memset(cnt,0,sizeof(cnt)); scanf("%d %d %d",&n,&m,&x); for(int i=1; i<=n; i++)tu[i].clear(); while(m--){ scanf("%d %d %d",&a,&b,&c); tu[a].push_back({b,c}); tu[b].push_back({a,c}); } while(x--){ scanf("%d %d %d",&a,&b,&c); tu[a].push_back({b,-c}); } if(spfa()==-1){ printf("YES\n"); } else printf("NO\n"); }return 0; }

    推荐阅读


    上一篇：虚虚实实 欧拉图

    下一篇：B-经商 并查集+背包