题目描述

N(2<=n<=200)个城市，M(1<=m<=40000)条无向边，你要找T(1<=T<=200)条从城市1到城市N的路，使得最长的边的长度最小，边不能重复用。

输入输出格式

输入格式：

 

第1行三个整数N,M,T用空格隔开。

第2行到P+1行，每行包括三个整数Ai,Bi,Li表示城市Ai到城市Bi之间有一条长度为Li的道路。

 

输出格式：

 

输出只有一行，包含一个整数，即经过的这些道路中最长的路的最小长度。

 

输入输出样例

输入样例#1：

7 9 21 2 22 3 53 7 51 4 14 3 14 5 75 7 11 6 36 7 3

输出样例#1：

5 正解是网络流。。。 所以就比较尴尬了。。 但是二分答案还是写出来了 等我哪天会了网络流一定回来A了这题。。

1 #include
       
         2 #include
        
          3 #include
         
           4 #include
          
            5 #include
           
             6 using namespace std; 7 const int MAXN=40001; 8 void read(int & n) 9 {10     char c='+';int x=0;bool flag=0;11     while(c<'0'||c>'9')12     {c=getchar();if(c=='-')flag=1;}13     while(c>='0'&&c<='9')14     {x=x*10+(c-48);c=getchar();}15     flag==1?n=-x:n=x;16 }17 int n,m,t;18 struct node19 {20     int u,v,w,nxt,use;21 }edge[MAXN];22 int head[MAXN];23 int num=1;24 void add_edge(int x,int y,int z)25 {26     edge[num].u=x;27     edge[num].v=y;28     edge[num].w=z;29     edge[num].nxt=head[x];30     head[x]=num++;31 }32 int maxl=-1,minl=0x7fff;33 int vis[MAXN];34 int map[201][201];35 int have[201][201];36 int bfs(int need)37 {38     queue
            
             q;39 q.push(1);40 while(q.size()!=0)41 {42 int p=q.front();43 q.pop();44 for(int i=head[p];i!=-1;i=edge[i].nxt)45 {46 if(edge[i].w<=need&&have[edge[i].u][edge[i].v]==0)47 {48 have[edge[i].u][edge[i].v]=1;49 have[edge[i].v][edge[i].u]=1;50 if(edge[i].v!=n)51 q.push(edge[i].v);52 vis[edge[i].v]++;53 }54 } 55 }56 if(vis[n]>=t)57 return 1;58 else 59 return 0;60 61 }62 int pd(int p)63 {64 memset(vis,0,sizeof(vis));65 memset(have,0,sizeof(have));66 if(bfs(p))67 return 1;68 else 69 return 0;70 }71 int main()72 {73 read(n);read(m);read(t);74 for(int i=1;i<=n;i++)75 head[i]=-1;76 for(int i=1;i<=m;i++)77 {78 int x,y,z;79 read(x);read(y);read(z);80 add_edge(x,y,z);81 add_edge(y,x,z);82 maxl=max(maxl,z);83 minl=min(minl,z);84 }85 int l=minl,r=maxl;86 while(l
             
              >1;89 if(pd(mid))90 r=mid;91 else l++;92 }93 printf("%d",l);94 return 0;95 }