| ||||||||||
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