首页 > > 程序设计 > C/C++ >

NOIP2013Day1T3 表示只能过一个点

2018-06-17 22:50:04来源：未知阅读 ()

•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         else
119         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         else
119         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 }