POJ2455 Secret Milking Machine

发表于 | 分类于 |

题目传送门

Description

有$n$个点，$m$条边。每条边有个长度。

FJ要从点$v_1$走到点$v_n$走$k$次，每条边只能走一次。（他有一条用于从点$v_n$会到点$v_1$的秘密通道，所以不用担心他为何能从点$v_1$走到点$v_n$走$k$次）

走$k$次中，走过的最长的那条路（是边，不是路径）最短可以有多短？

Input

第一行：三个整数$n$、$m$和$k$，表示点数、边数和走几次。

接下来$m$行：每行有三个整数$u$、$v$、$l$表示点$u$到点$v$有条长度为$l$的边。

Output

一个整数：最长那条图最短的长度。

Solution

求最长的最短，二分。

每条边只走一次所以流量为$1$。

每次二分出一个答案$mid$。

跑网络流，但只跑长度不大于$mid$的边。

看总流量是否可以不少于为$k$。

Code

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
#include<cstdio>
#include<cstdlib>
#include<string.h>
#include<algorithm>
#define oo 100000
using namespace std;
const int maxn=210;
const int maxp=500100;
int N,P,T;
struct EDGE
{
	int ap,L,flow;
	EDGE *next,*fe;
}edge[maxp],*ind[maxn];
int el=-1;
void input(int u,int v,int l,int flow)
{
	edge[++el].ap=v;
	edge[el].flow=flow;
	edge[el].L=l;
	edge[el].next=ind[u];
	ind[u]=&edge[el];
	edge[el].fe=&edge[el^1];
}
int level[maxn],q[maxn],Time=0;
bool bfs(int x)
{
	int h1=1,t1=2;
	q[1]=1;
	level[1]=++Time;
	while(h1<t1)
	{
		int u=q[h1];
		for(EDGE *k=ind[u];k!=NULL;k=k->next)
		{
			int v=k->ap;
			if(k->L>x||k->flow==0||level[v]>=level[1]) continue;
			level[v]=level[u]+1;
			Time=max(Time,level[v]);
			if(v==N) return 1;
			q[t1++]=v;
		}
		h1++;
	}
	return 0;
}
int dfs(int u,int flow,int x)
{
	if(u==N) return flow;
	int sum=0;
	for(EDGE *k=ind[u];k!=NULL;k=k->next)
	{
		int v=k->ap;
		if(k->L>x||k->flow==0||level[v]<=level[u]) continue;
		
		int d=dfs(v,min(flow-sum,k->flow),x);
		
		sum+=d;
		k->flow-=d;
		k->fe->flow+=d;
		if(flow<=sum) break;
	}
	level[u]=0;
	return sum;
}
bool check_dinic(int x)
{
	int sum=0;
	while(bfs(x))
		sum+=dfs(1,oo,x);
	return T<=sum ? 1 : 0;
}
void init()
{
	for(int i=0;i<=el;i++) edge[i].flow=1;
}
int main()
{
	int l=oo,r=0;
	scanf("%d%d%d",&N,&P,&T);
	for(int i=1;i<=P;i++)
	{
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		r=max(r,z);
		l=min(l,z);
		input(x,y,z,1);
		input(y,x,z,1);
	}
	while(l<r-1)
	{
		init();
		int mid=(l+r)>>1;
		if(check_dinic(mid)) r=mid;
		else l=mid;
	}
	printf("%d",r);
	return 0;
}