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 |
Re:c++ 选手一定要用G++提交!!!!!!!!!!!!!否则会wa!<---血的教训(附代码,最小瓶颈路,n²)(绝对没有不连通图)In Reply To:c++ 选手一定要用G++提交!!!!!!!!!!!!!否则会wa!<---血的教训(附代码,最小瓶颈路,n²)(绝对没有不连通图) Posted by:lizitong at 2014-07-20 19:24:57 还真是。。。。。。 #include <iostream> #include <algorithm> #include <vector> #include <climits> #include <cstdio> #include <cstdlib> #include <queue> #include <string> #include <cstring> using namespace std; #define MAXN 1100 int gra[MAXN][MAXN], maxl[MAXN][MAXN], visE[MAXN][MAXN]; int dis[MAXN], pre[MAXN]; int vis[MAXN]; int n,m; int T; int ans=0; bool flag; int main(){ cin>>T; for(int t=1;t<=T;t++){ cin>>n>>m; ans=0; flag=true; for(int i=0;i<n;i++){ dis[i]=INT_MAX; vis[i]=0; pre[MAXN]=-1; for(int j=0;j<n;j++){ gra[i][j]=INT_MAX; maxl[i][j]=INT_MIN; visE[i][j]=0; } } for(int i=0;i<m;i++){ int a,b,c; scanf("%d%d%d",&a,&b,&c); a--;b--; gra[a][b]=gra[b][a]=c; } dis[0]=0; for(int i=0;i<n;i++){ int minD=INT_MAX, minI; for(int j=0;j<n;j++){ if(vis[j]==0 and dis[j]<minD){ minD=dis[j]; minI=j; } } vis[minI]=1; visE[pre[minI]][minI]=visE[minI][pre[minI]]=1; ans+=minD; for(int j=0;j<n;j++){ if(vis[j]==0 and gra[minI][j]<INT_MAX){ if(dis[j]>gra[minI][j]){ pre[j]=minI; dis[j]=gra[minI][j]; } } } for(int j=0;j<n;j++){ if(vis[j]==1 and j!=minI){ maxl[j][minI]=max(maxl[j][minI], minD); if(gra[minI][j]<INT_MAX and visE[minI][j]==0 and gra[minI][j]==maxl[j][minI]){ flag=false; break; } } } if(flag==false)break; } if(flag){ cout<<ans<<endl; } else{ cout<<"Not Unique!"<<endl; } } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator