首页 > 代码库 > NOIP2013Day1T3 表示只能过一个点
NOIP2013Day1T3 表示只能过一个点
•A 国有 n 座城市，编号从 1 到 n，城市之间有 m 条双向道路。每一条道路对车辆都有重量限制，简称限重。现在有 q 辆货车在运输货物，司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<algorithm> 6 using namespace std; 7 struct node 8 { 9 int u; 10 int v; 11 int w; 12 }edge[1001]; 13 int num=1; 14 int maxn[101][101]; 15 int f[1001]; 16 int x,y; 17 int ans=0x7fffffff; 18 int cmp(const node &a,const node &b) 19 { 20 return a.w>b.w; 21 } 22 int find(int x) 23 { 24 if(x!=f[x]) 25 f[x]=find(f[x]); 26 return f[x]; 27 } 28 void unionn(int x,int y) 29 { 30 int fx=find(x); 31 int fy=find(y); 32 f[fx]=fy; 33 } 34 int vis[10001]; 35 int n,m; 36 int flag=0; 37 int dfs(int p) 38 { 39 if(p==y) 40 flag=1; 41 else 42 { 43 for(int i=1;i<=n;i++) 44 { 45 if(vis[i]==0&&maxn[p][i]!=0x7fffffff) 46 { 47 vis[i]=1; 48 ans=min(ans,maxn[p][i]); 49 dfs(i); 50 vis[i]=0; 51 ans=min(ans,maxn[p][i]); 52 } 53 54 } 55 } 56 //printf("%d",ans); 57 } 58 int main() 59 { 60 61 scanf("%d%d",&n,&m); 62 for(int i=1;i<=n;i++)f[i]=i; 63 for(int i=1;i<=m;i++) 64 { 65 scanf("%d%d%d",&edge[num].u,&edge[num].v,&edge[num].w); 66 num++; 67 } 68 sort(edge+1,edge+num,cmp); 69 int k=0; 70 for(int i=1;i<=num;i++) 71 { 72 if(find(edge[i].u)!=find(edge[i].v)) 73 { 74 unionn(edge[i].u,edge[i].v); 75 //maxn[edge[i].v]=max(edge[i].w,maxn[edge[i].v]); 76 //maxn[edge[i].u]=max(edge[i].w,maxn[edge[i].u]); 77 maxn[edge[i].u][edge[i].v]=max(maxn[edge[i].u][edge[i].v],edge[i].w); 78 maxn[edge[i].v][edge[i].u]=max(maxn[edge[i].u][edge[i].v],edge[i].w); 79 k++; 80 } 81 if(k==n-1)break; 82 } 83 for(int i=1;i<=n;i++) 84 for(int j=1;j<=n;j++) 85 { 86 if(maxn[i][j]==0) 87 maxn[i][j]=0x7fffffff; 88 } 89 /*for(int k=1;k<=n;k++) 90 { 91 for(int i=1;i<=n;i++) 92 { 93 for(int j=1;j<=n;j++) 94 { 95 if(maxn[i][k]!=0x7fffffff&&maxn[k][j]!=0x7fffffff) 96 if(maxn[i][j]>maxn[i][k]+maxn[k][j]) 97 maxn[i][j]=maxn[i][k]+maxn[k][j]; 98 } 99 }100 }*/101 int q;102 scanf("%d",&q);103 for(int i=1;i<=q;i++)104 {105 flag=0;106 memset(vis,0,sizeof(vis));107 ans=0x7fffffff;108 scanf("%d%d",&x,&y);109 dfs(x);110 //printf("*******************************\n");111 if(ans!=0x7fffffff&&flag==1)112 printf("%d\n",ans);113 else 114 printf("-1\n");115 //printf("*******************************\n");116 /*if(maxn[x][y]==0)117 printf("-1\n");118 else119 printf("%d\n",maxn[x][y]);*/120 /*for(int j=x;j<=y;j++)121 {122 if(maxn[j]<maxnnow&&maxn[j]!=0)123 maxnnow=maxn[j];124 }125 if(maxnnow==0x7ffff)printf("-1\n");126 else printf("%d\n",maxnnow);*/127 }128 return 0;129 }
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<algorithm> 6 using namespace std; 7 struct node 8 { 9 int u; 10 int v; 11 int w; 12 }edge[1001]; 13 int num=1; 14 int maxn[101][101]; 15 int f[1001]; 16 int x,y; 17 int ans=0x7fffffff; 18 int cmp(const node &a,const node &b) 19 { 20 return a.w>b.w; 21 } 22 int find(int x) 23 { 24 if(x!=f[x]) 25 f[x]=find(f[x]); 26 return f[x]; 27 } 28 void unionn(int x,int y) 29 { 30 int fx=find(x); 31 int fy=find(y); 32 f[fx]=fy; 33 } 34 int vis[10001]; 35 int n,m; 36 int flag=0; 37 int dfs(int p) 38 { 39 if(p==y) 40 flag=1; 41 else 42 { 43 for(int i=1;i<=n;i++) 44 { 45 if(vis[i]==0&&maxn[p][i]!=0x7fffffff) 46 { 47 vis[i]=1; 48 ans=min(ans,maxn[p][i]); 49 dfs(i); 50 vis[i]=0; 51 ans=min(ans,maxn[p][i]); 52 } 53 54 } 55 } 56 //printf("%d",ans); 57 } 58 int main() 59 { 60 61 scanf("%d%d",&n,&m); 62 for(int i=1;i<=n;i++)f[i]=i; 63 for(int i=1;i<=m;i++) 64 { 65 scanf("%d%d%d",&edge[num].u,&edge[num].v,&edge[num].w); 66 num++; 67 } 68 sort(edge+1,edge+num,cmp); 69 int k=0; 70 for(int i=1;i<=num;i++) 71 { 72 if(find(edge[i].u)!=find(edge[i].v)) 73 { 74 unionn(edge[i].u,edge[i].v); 75 //maxn[edge[i].v]=max(edge[i].w,maxn[edge[i].v]); 76 //maxn[edge[i].u]=max(edge[i].w,maxn[edge[i].u]); 77 maxn[edge[i].u][edge[i].v]=max(maxn[edge[i].u][edge[i].v],edge[i].w); 78 maxn[edge[i].v][edge[i].u]=max(maxn[edge[i].u][edge[i].v],edge[i].w); 79 k++; 80 } 81 if(k==n-1)break; 82 } 83 for(int i=1;i<=n;i++) 84 for(int j=1;j<=n;j++) 85 { 86 if(maxn[i][j]==0) 87 maxn[i][j]=0x7fffffff; 88 } 89 /*for(int k=1;k<=n;k++) 90 { 91 for(int i=1;i<=n;i++) 92 { 93 for(int j=1;j<=n;j++) 94 { 95 if(maxn[i][k]!=0x7fffffff&&maxn[k][j]!=0x7fffffff) 96 if(maxn[i][j]>maxn[i][k]+maxn[k][j]) 97 maxn[i][j]=maxn[i][k]+maxn[k][j]; 98 } 99 }100 }*/101 int q;102 scanf("%d",&q);103 for(int i=1;i<=q;i++)104 {105 flag=0;106 memset(vis,0,sizeof(vis));107 ans=0x7fffffff;108 scanf("%d%d",&x,&y);109 dfs(x);110 //printf("*******************************\n");111 if(ans!=0x7fffffff&&flag==1)112 printf("%d\n",ans);113 else 114 printf("-1\n");115 //printf("*******************************\n");116 /*if(maxn[x][y]==0)117 printf("-1\n");118 else119 printf("%d\n",maxn[x][y]);*/120 /*for(int j=x;j<=y;j++)121 {122 if(maxn[j]<maxnnow&&maxn[j]!=0)123 maxnnow=maxn[j];124 }125 if(maxnnow==0x7ffff)printf("-1\n");126 else printf("%d\n",maxnnow);*/127 }128 return 0;129 }
NOIP2013Day1T3 表示只能过一个点
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。