程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> POJ2387求負權值

POJ2387求負權值

編輯:關於C++

這道題是一個農場有F個神奇的農場
農場有N個點,M條路,W個蟲洞。蟲洞能回溯時間。
問能不能從某個點出發,通過路和蟲洞,回到原點,時間比原來早。

我第一思路是用bellman-ford算法,可以求是否出現負權值情況來做。
提交了好幾次不對,發現坑爹之處是M條路是雙向的,W個蟲洞是單向的,理解了這個以後就能做了。它是要求某個點,所以要便利所有點來做bellman算法。

#include 
#include 
#define INF 0x3f3f3f3f
using namespace std;
struct edge
{
    int from,to,cost;
    edge(int f,int t,int c):from(f),to(t),cost(c){};
    edge(){}
};
edge es[3000];
int d[550];
int F,N,M,W;
void bellman(){
    for (int k = 1; k <= N; ++k)
    {
        memset(d,INF,sizeof(d));
        d[k]=0;
        int flag=1;
        while(flag){
            flag=0;
            for (int i = 0; i < M+W; ++i)
            {
                edge e=es[i];
                if (d[e.from]!=INF&&d[e.from]+e.cost=0)
                {
                    d[e.to]=d[e.from]+e.cost;
                    flag=1;
                }               
                if (i=0)
                {
                    d[e.from]=d[e.to]+e.cost;
                    flag=1;
                }
            }
        }
        if (d[k]<0){
                printf("YES\n");
                return ;
        }
    }
    printf("NO\n");
}
int main(int argc, char const *argv[])
{
    scanf("%d",&F);
    int x,y,w;
    while(F--){
        scanf("%d%d%d",&N,&M,&W);
        int i;
        for ( i = 0; i < M; ++i)
        {
            scanf("%d%d%d",&x,&y,&w);
            es[i].from=x;
            es[i].to=y;
            es[i].cost=w;
        }
        for (; i 
  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved