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

help,并查集+差分约束,死活wa,求检查……

Posted by orbby at 2010-12-14 16:43:40 on Problem 2983
#include<iostream>
#include<stdio.h>
using namespace std;
#define MM 100000

int n,m;

int bei[1000][2];
int tu[1000][1000];
int edge[100000][3];
int index;

int d[1000];
int find(int &a);

bool duan()
{
	for(int i=0;i<1000;i++)
	{
		d[i]=0;
	}

	for(int i=0;i<n;i++)
	{
		bool change=false;
		for(int j=0;j<m;j++)
		{
			int a=edge[j][0];
			int b=edge[j][1];
			int c=edge[j][2];

			if(d[b]>d[a]+c)
			{
				change=true;
				d[b]=d[a]+c;
			}
		}
		if(!change)
		{
			return true;
		}
	}

	for(int j=0;j<m;j++)
	{
			int a=edge[j][0];
			int b=edge[j][1];
			int c=edge[j][2];

			if(d[b]>d[a]+c)
			{
				return false;
			}
	}
	return true;
}


bool bian()
{
	index=0;
	for(int i=0;i<1000;i++)
	{
		for(int j=0;j<1000;j++)
		{
			if(tu[i][j])
			{
				int a=i;
				int b=j;
				int c=1;
				int ja=find(a);
				int jb=find(b);
				c+=ja;
				c-=jb;

				edge[index][0]=a;
				edge[index][1]=b;
				edge[index][2]=-c;
				index++;
				//cout<<a<<"  "<<b<<"  "<<c<<endl;
			}
		}
	}
	m=index;
}

int find(int &a)
{
	int a_back=a;
	int juli=0;
	int pa=bei[a][0];
	while(pa!=-1)
	{
		juli+=bei[a][1];
		a=pa;
		pa=bei[a][0];
	}
	return juli;
}

bool uni(int a,int b,int juli)
{
	if((a==b))
	{
		if(juli)
			return false;
		return true;

	}

	bei[b][0]=a;
	bei[b][1]=juli;
}

bool u(int a,int b,int c)
{
	int ja=find(a);
	int jb=find(b);
	return uni(a,b,ja+c-jb);
}

int main()
{
	while(cin>>n)
	{
		cin>>m;
		for(int i=0;i<1000;i++)
		{
			bei[i][0]=-1;
		}

		for(int i=0;i<1000;i++)
		{
			for(int j=0;j<1000;j++)
			{
				tu[i][j]=0;
			}
		}

		int dian=0;
		bool out=false;
		for(int i=0;i<m;i++)
		{
			char r;
			scanf("\n%c",&r);
			if(r=='P')
			{
				int a,b,c;
				scanf("%d %d %d",&a,&b,&c);
				a--;
				b--;

				if(!out)
				{
					out=!u(a,b,c);
				}
			}

			else
			{
				int a,b;
				scanf("%d %d",&a,&b);
				a--;
				b--;
				tu[a][b]=1;
			}

		}
		if(out)
		{
			cout<<"Unreliable"<<endl;
			continue;
		}

		bian();

		for(int i=0;i<1000;i++)
		{
			if(bei[i][0]==-1)
			{
				dian++;
			}
		}
		n=dian;
		if(duan())
		{
			cout<<"Reliable"<<endl;
		}
		else
		{
			cout<<"Unreliable"<<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