Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

类型打错导致WA n次,附上SPFA邻接表代码,祭奠我的黑眼圈。。

Posted by _Dante_ at 2013-08-12 02:15:42 on Problem 1860
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <map>
#include <cmath>
#include <set>
#include <climits>
#define INF 0x7fffffff
#define finc(i,a,b) for(i=a;i<=b;i++)
#define fdec(i,a,b) for(i=a;i>=b;i--)
using namespace std;
const int MAXN=502,MAXM=5205;
int N,M,S,T,W;
double V;
struct Edge  //使用数组模拟邻接表存储边信息
{
    int a,b;
    double r,c;
    int next;
}D[MAXM];

int list[MAXN],tot;
double dist[MAXN];
queue<int>q;
int cnt[MAXN];
bool f[MAXN];

void add(int a,int b,double r,double c) //构建邻接表
{
    D[++tot].a=a;
    D[tot].b=b;
    D[tot].c=c;
    D[tot].r=r;
    D[tot].next=list[a];
    list[a]=tot;
}
bool init()
{
    int i;
    if(cin>>N>>M>>S>>V);
    else return false;

    for(int i=1;i<=M;i++)
    {
        int a,b;
        double c,r;
        cin>>a>>b>>r>>c;
        add(a,b,r,c);
        cin>>r>>c;
        add(b,a,r,c);           //如果为有向图则不加此句
    }
    return true;
}

bool spfa()
{
    for(int i=1;i<=N;i++)    //初始化距离
    dist[i]=0;
    dist[S]=V;
    q.push(S);f[S]=0;
    while(q.size())
    {
        if(dist[S]>V) return false;
        int a=q.front(),b;        //取出队首元素
        q.pop();
        for(int k=list[a]; k; k=D[k].next)    //枚举其每条出边进行松弛
        {
            b=D[k].b;
            if(dist[b]<(dist[a]-D[k].c)*D[k].r)
            {
                dist[b]=(dist[a]-D[k].c)*D[k].r;
                if(f[b] == 0)
                {
                    f[b]=1;
                    q.push(b);
                }
                cnt[b]++;         //记录每个点入队次数
                if(cnt[b]>N)
                    return false;   //如果某个点入队超过N次,则有负环
            }
        }
        f[a]=0;
    }
    return true;
}
int main()
{

    while(1){
        tot=0;
        while(!q.empty()) q.pop();
        memset(cnt,0,sizeof(cnt));
        memset(list,0,sizeof(list));
        memset(f,false,sizeof(f));
    if(!init()) break;
        if(spfa())
            cout<<"NO"<<endl;
        else    cout<<"YES"<<endl;
    }
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator