【Usaco05Mar】Ombrophobic Bovines

来源和评测点

USACO 2005 March Gold
Bzoj1738
Poj2391
Caioj1118

题目

【题目大意】
下雨了,有F(1<=F<=200)个牛棚,这F个牛棚之间有P(1<=P<=1500)条无向边(有耗时)
每个牛棚有两个值A和B(A表示一开始这个牛棚有A头牛,B表示下雨时该牛棚最多可以容纳B头牛躲雨)。
问最少需要提前多少时间响“下雨警告”才能让所有牛在下雨前都能够找到可以遮雨的地方。

重点句:
The paths are wide,so that any number of cows can traverse a path in either direction. 无向边
Fields are small compared to the paths and require no time for cows to traverse. 将牛棚看作点
【输入格式】
两个整数: F 和 P
接下来F行,第i行两个整数A和B(A、B的范围都是:0..1000)描述第i个牛棚
接下来P行,每行三个整数。X Y L,表示牛棚X和牛棚Y之间有一条边,耗时是L(1<=L<=1,000,000,000)
【输出格式】
输出一行,即为最短的时间,如果无法使得所有牛都能够有地方避雨,那么输出 “-1”
【输入样例】
3 4
7 2
0 4
2 6
1 2 40
3 2 70
2 3 90
1 3 120
【输出样例】
110
【样例解释】
牛棚1安排4头牛到牛棚2,牛棚1再安排1头牛走到牛棚2,再走到牛棚3避雨。

分析

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

这道题建议大家像我一样仔细想想,
别急着看题解,虽然你到我这个页面很可能是来膜题解的

由于边比较复杂,但又是无向图
考虑Floyd获得两点之间最短耗时
然后两点之间只存在一条边了

原问题转化成:
选一些边来满足条件并且最长边最小
条件为牛跑来跑去后每个牛棚能容纳下

考虑二分答案,从而得到满足的边,跑一遍网络流验证解的可行性

构图:
从汇点到各个左牛棚,容量是每个牛棚原本的牛数量
拆点,从左牛棚连到右牛棚,表示可以通过去,容量是无限
从右牛棚到汇点,容量是牛棚最后的最大容纳

假如最大流=牛的数量F 表示可行

记得自己可以连自己

代码

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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
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=510,MAXM=110000;
struct pt
{
int h;
int hou;
}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=0;
e[ln].g=p[y].hou;p[y].hou=ln;
e[ln-1].oth=ln;e[ln].oth=ln-1;
}
int st,ed;
int lst[MAXN];
bool bfs()
{
for(int i=1;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)
{
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(p[y].h==p[x].h+1 and e[k].c>0 and t<f)
{
int tt=dfs(y,mymin(f-t,e[k].c));
t+=tt;e[k].c-=tt;e[e[k].oth].c+=tt;
}
}
if(t==0) p[x].h=0;
return t;
}
/*
1~n 左牛棚
n+1~n+n 右牛棚
n+n+1 源点
n+n+2 汇点
*/
int n;
int alc;
int aa[MAXN],bb[MAXN];
ll cst[MAXN][MAXN];
bool check(ll mid)
{
ln=0;for(int i=1;i<=ed;i++) p[i].hou=0;
for(int i=1;i<=n;i++)
{
ins(st,i,aa[i]);ins(i,n+i,INF);ins(n+i,ed,bb[i]);
for(int j=1;j<=n;j++) if(cst[i][j]<=mid) ins(i,n+j,INF);
}
int ans=0;
while(bfs()) ans+=dfs(st,INF);
//printf("mid=%d ans=%d alc=%d\n",mid,ans,alc);
return ans==alc;
}
int main()
{
memset(cst,63,sizeof(cst));
int m;scanf("%d%d",&n,&m);
st=n+n+1,ed=n+n+2;
for(int i=1;i<=n;i++) scanf("%d%d",&aa[i],&bb[i]),alc+=aa[i];
for(int i=1;i<=m;i++)
{
int x,y;ll c;scanf("%d%d%lld",&x,&y,&c);
if(c<cst[x][y]) cst[x][y]=cst[y][x]=c;
}
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
ll nt=cst[i][k]+cst[k][j];
if(nt<cst[i][j]) cst[i][j]=nt;
}
ll l=0,r=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=i-1;j++)
if(cst[i][j]!=cst[0][0] and cst[i][j]>r) r=cst[i][j];
ll ans=-1;
while(l<=r)
{
ll mid=(l+r)>>1;
if(check(mid)) ans=mid,r=mid-1;
else l=mid+1;
}
printf("%lld",ans);
}

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

哪怕是一杯奶茶,也将鼓励我继续创作!
0%