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

普通边是双向的,虫洞的边的单向………………SPFA水过

Posted by jhb0815 at 2014-07-31 15:42:57 on Problem 3259
普通边是双向的,虫洞的边的单向………………
初入SPFA,没想到从u到v可以有双向边+单向边……还是需要练啊
基本想法:SPFA判断负环即可。
贴个代码:
#include<iostream>
#include<algorithm>
#include<queue>

#define MAX_NODE 5200
#define MAX_EDGE 10086

using namespace std;

class EDGE
{
public :
	int V,Next,Weight;
	EDGE():V(0),Next(0),Weight(0){}
}Edge[MAX_EDGE];

int Head[MAX_NODE],K = 0;

bool SPFA(int Sta,int CountNode);
void AddEdge(int u,int v,int weight);

int main(void)
{
	int T = 0;
	cin>>T;
	while(T --)
	{
		memset(Head,-1,sizeof(Head));
		K = 0;
		int P = 0,E = 0,W = 0;
		scanf("%d %d %d",&P,&E,&W);
		for(int i = 0;i < E;i ++)
		{
			int U = 0,V = 0,Weight = 0;
			scanf("%d %d %d",&U,&V,&Weight);
			AddEdge(U,V,Weight);
			AddEdge(V,U,Weight);
		}
		for(int i = 0;i < W;i ++)
		{
			int U = 0,V = 0,Weight = 0;
			scanf("%d %d %d",&U,&V,&Weight);
			AddEdge(U,V,0 - Weight);
		}
		/*bool Flag= true;
		for(int i = 1;i <= P;i ++)
		{
			if(SPFA(i,P))
			{
				printf("YES\n");
				Flag = false;
				break;
			}
		}
		if(Flag)
			printf("NO\n");*/
		if(SPFA(1,P))
			cout<<"YES"<<endl;
		else 
			cout<<"NO"<<endl;
	}
	return 0;
}
bool SPFA(int Sta,int CountNode)
{
	queue<int>Que;
	bool Visit[MAX_NODE];
	int Dist[MAX_NODE];
	int Count[MAX_NODE];
	memset(Count,0,sizeof(Count));
	memset(Visit,true,sizeof(Visit));
	memset(Dist,0x3f,sizeof(Dist));
	Dist[Sta] = 0,Visit[Sta] = false;
	Que.push(Sta);Count[Sta] ++;
	while(! Que.empty())
	{
		int Front = Que.front();
		Que.pop();
		Visit[Front] = true;
		for(int i = Head[Front];i != -1;i = Edge[i].Next)
		{
			int Temp = Edge[i].V;
			if(Dist[Temp] > Dist[Front] + Edge[i].Weight)
			{
				Dist[Temp] = Dist[Front] + Edge[i].Weight;
				if(Visit[Temp])
				{
					Count[Temp] ++;
					Visit[Temp] = false;
					Que.push(Temp);
					if(Count[Temp] >= CountNode) return true;
				}
			}
		}
	}
	return false;
}
void AddEdge(int u,int v,int weight)
{
	Edge[K].V = v;
	Edge[K].Weight = weight;
	Edge[K].Next = Head[u];
	Head[u] = K ++;
}

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