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

P1401 城市（30分，正解网络流）

2018-06-17 22:20:53来源：未知阅读 ()

题目描述

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：

输出样例#1：

5

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

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<queue>
 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 node
19 {
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<int>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<r)
87     {
88         int mid=(l+r)>>1;
89         if(pd(mid))
90             r=mid;
91         else l++;
92     }
93     printf("%d",l);
94     return 0;
95 }