专栏首页数据结构与算法P1401 城市(30分,正解网络流)

P1401 城市(30分,正解网络流)

题目描述

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 2
1 2 2
2 3 5
3 7 5
1 4 1
4 3 1
4 5 7
5 7 1
1 6 3
6 7 3

输出样例#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 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 185. [USACO Oct08] 挖水井

    185. [USACO Oct08] 挖水井 ★★   输入文件:water.in   输出文件:water.out 简单对比 时间限制:1 s   内存限制:...

    attack
  • 2488 绿豆蛙的归宿

    2488 绿豆蛙的归宿 时间限制: 1 s 空间限制: 64000 KB 题目等级 : 黄金 Gold 题目描述 Description   随着...

    attack
  • P1294 高手去散步

    题目背景 高手最近谈恋爱了。不过是单相思。“即使是单相思,也是完整的爱情”,高手从未放弃对它的追求。今天,这个阳光明媚的早晨,太阳从西边缓缓升起。于是它找到高手...

    attack
  • 185. [USACO Oct08] 挖水井

    185. [USACO Oct08] 挖水井 ★★   输入文件:water.in   输出文件:water.out 简单对比 时间限制:1 s   内存限制:...

    attack
  • 186. [USACO Oct08] 牧场旅行

    157. [USACO Nov07] 奶牛跨栏 186. [USACO Oct08] 牧场旅行 ★★   输入文件:pwalk.in   输出文件:pwalk....

    attack
  • P1294 高手去散步

    题目背景 高手最近谈恋爱了。不过是单相思。“即使是单相思,也是完整的爱情”,高手从未放弃对它的追求。今天,这个阳光明媚的早晨,太阳从西边缓缓升起。于是它找到高手...

    attack
  • 1231 最优布线问题

    1231 最优布线问题 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 白银 Silver 题目描述 Description 学...

    attack
  • BZOJ2683: 简单题(cdq分治 树状数组)

    你有一个N*N的棋盘,每个格子内有一个整数,初始时的时候全部为0,现在需要维护两种操作:

    attack
  • 网络最大流算法—最高标号预流推进HLPP

    吐槽 这个算法。。 怎么说........ 学来也就是装装13吧。。。。 长得比EK丑 跑的比EK慢 写着比EK难 思想 大家先来猜一下这个算法的思想吧:joy...

    attack
  • POj 1797 Heavy Transportation

    题意:求从1-n所能承受的最大重量是多少,其最大重量就是1-n通路的最小边 分析:求最大生成树的最小边,排序的时候按照权值从大到小派,然后生成树,知道找到1-n...

    用户1624346

扫码关注云+社区

领取腾讯云代金券