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

Re:c++ 选手一定要用G++提交!!!!!!!!!!!!!否则会wa!<---血的教训(附代码,最小瓶颈路,n²)(绝对没有不连通图)

Posted by zxtregister at 2016-08-04 16:16:43 on Problem 1679
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:
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