心如止水
Je n'ai pas le temps
posts - 400,comments - 130,trackbacks - 0
SPFA判负权回路。
以下是我的代码:
#include<queue>
#include
<cstdio>
#include
<cstring>
using namespace std;
const int kMaxn(507);
const int kMaxm(5207);
const long long kInf(0x7f7f7f7f7f7f7f7fll);

struct Edge
{
    
int v,w;
};

int n,m,w;
int cnt,first[kMaxn],next[kMaxm];Edge e[kMaxm];

void AddEdge(int u,int v,int w)
{
    cnt
++;
    e[cnt].v
=v;e[cnt].w=w;
    next[cnt]
=first[u];
    first[u]
=cnt;
}

bool SPFA()
{
    
long long dist[kMaxn];
    queue
<int> q;
    
int num[kMaxn]={0};
    
bool inq[kMaxn]={false};
    
for(int i=1;i<=n;i++)
        dist[i]
=(i==1?0:kInf);
    q.push(
1);
    inq[
1]=true;
    num[
1]++;
    
while(!q.empty())
    {
        
int u(q.front());q.pop();
        inq[u]
=false;
        
if(num[u]>n)
            
return true;
        
for(int i=first[u];i!=-1;i=next[i])
        {
            
int v(e[i].v),w(e[i].w);
            
if(dist[v]>dist[u]+w)
            {
                dist[v]
=dist[u]+w;
                
if(!inq[v])
                {
                    q.push(v);
                    inq[v]
=true;
                    num[v]
++;
                }
            }
        }
    }
    
return false;
}

int main()
{
    
int T;
    scanf(
"%d",&T);
    
while(T--)
    {
        scanf(
"%d%d%d",&n,&m,&w);
        cnt
=0;
        memset(first,
-1,sizeof(first));
        
for(int i=1;i<=m;i++)
        {
            
int u,v,w;
            scanf(
"%d%d%d",&u,&v,&w);
            AddEdge(u,v,w);
            AddEdge(v,u,w);
        }
        
for(int i=1;i<=w;i++)
        {
            
int u,v,w;
            scanf(
"%d%d%d",&u,&v,&w);
            AddEdge(u,v,
-w);
        }

        
if(SPFA())
            printf(
"YES\n");
        
else
            printf(
"NO\n");
    }

    
return 0;
}
posted on 2011-07-31 09:51 lee1r 阅读(239) 评论(0)  编辑 收藏 引用 所属分类: 题目分类:图论

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理