【Poj2455】【Bzoj1733】Secret Milking Machine

来源和评测点

USACO 2005 February Gold
Poj2455
Bzoj1733
Caioj1117

题目

【题目大意】
给出N(2<=N<=200)个点和P(1<=P<=40000)条双向边,每条边的长度为(0~1000000)
现在要求选出T(1<=T<=200)条“1至N”的路径,任意两条路径上的边不能重复
并且要求这些路径中的最长边的长度最小
注意:两个点之间有可能多条边,出发点是1,终点是N
【输入格式】
第一行三个整数: N,P,T
下来P行,每行三个整数x,y,L,描述一条边:从点x到y的双向边,长度为Li
【输出格式】
求这T条路径中的的最长边的最小值
【输入样例】
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
【输出样例】
5
提示:样例最后选择了两条路径 1-2-3-7 和 1-6-7 最长的路是5.

分析

网络流教程和题目分类参见:
【OI之路】03图论算法-4网络流
其他网络流题目参见:Tag-网络流

注意两个概念:边 和 路径(路径是由多条边组成,当然可以是一条边)
这题需要建立模型
重点是二分,在同学的提醒下想到这个,然后就想通了
就是二分最长边长度,满足结果(可行性)有序性
因为每条边只能去一次,边权为1即可

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int INF=0x3f3f3f3f;
int mymin(int x,int y) {return x<y?x:y;}
int mymax(int x,int y) {return x>y?x:y;}
const int MAXN=210,MAXM=81000;
struct pt
{
int hou;
int h;
}p[MAXN];
struct rod
{
int y,c,g;
int oth;
}e[MAXM];
int ln;
void ins(int x,int y,int c)
{
ln++;
e[ln].y=y;e[ln].c=c;
e[ln].g=p[x].hou;p[x].hou=ln;
ln++;
e[ln].y=x;e[ln].c=c;
e[ln].g=p[y].hou;p[y].hou=ln;
e[ln-1].oth=ln;e[ln].oth=ln-1;
}
int m,T;
int st,ed;
int lst[MAXN];
bool bfs()
{
for(int i=st;i<=ed;i++) p[i].h=0;
int tou=1,wei=1;
lst[1]=st;p[st].h=1;
while(tou<=wei)
{
int x=lst[tou];
for(int k=p[x].hou;k>0;k=e[k].g)
{
int y=e[k].y;
if(p[y].h==0 and e[k].c>0)
{
p[y].h=p[x].h+1;
lst[++wei]=y;
}
}
tou++;
}
return p[ed].h>0;
}
int dfs(int x,int f)
{
//printf("---x=%d f=%d\n",x,f);
if(x==ed) return f;
int t=0;
for(int k=p[x].hou;k>0;k=e[k].g)
{
int y=e[k].y;
if(t<f and e[k].c>0 and p[y].h==p[x].h+1)
{
int fs=dfs(y,mymin(e[k].c,f-t));
t+=fs;e[k].c-=fs;e[e[k].oth].c+=fs;
}
}
if(t==0) p[x].h=0;
return t;
}
int xx[MAXM],yy[MAXM],cc[MAXM];
bool check(int mid)
{
for(int i=st;i<=ed;i++) p[i].hou=0;
ln=0;
for(int i=1;i<=m;i++)
if(cc[i]<=mid)
ins(xx[i],yy[i],1);
int ans=0;
while(bfs()) ans+=dfs(st,INF);
return ans>=T;
}
int main()
{
int n;scanf("%d%d%d",&n,&m,&T);
int l=INF,r=-INF;
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&xx[i],&yy[i],&cc[i]);
l=mymin(l,cc[i]);r=mymax(r,cc[i]);
}
st=1,ed=n;
int ans=-1;
while(l<=r)
{
int mid=(l+r)>>1;
if(check(mid)) ans=mid,r=mid-1;
else l=mid+1;
}
printf("%d",ans);
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/7731.html
转载请注明出处,谢谢!