| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
help,并查集+差分约束,死活wa,求检查……#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator