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