P2402 奶牛隐藏【二分】【最大流】
题目背景
这本是一个非常简单的问题，然而奶牛们由于下雨已经非常混乱，无法完成这一计算，于是这个任务就交给了你。(奶牛混乱的原因看题目描述)
题目描述
在一个农场里有 nn 块田地。某天下午，有一群牛在田地里吃草，他们分散在农场的诸多田地上，农场由 mm 条无向的路连接，每条路有不同的长度。
突然，天降大雨，奶牛们非常混乱，想要快点去躲雨。已知每个田地都建立有一个牛棚，但是每个牛棚只能容纳一定数量的牛躲雨，如果超过这个数量，那多出的牛只能去别的田地躲雨。奶牛们每移动 11 的距离花费 11 时间，奶牛们想知道它们全部都躲进牛棚，最少需要多少时间。(即最后一头奶牛最少要花多久才能躲进牛棚)。
输入格式
第一行有两个整数，分别代表田地数 nn 和道路数 mm。
接下来 nn 行，每行两个整数，第 (i + 1)(i+1) 行的整数 s_i, p_isi,pi 分别表示第 ii 块田地的牛的数量以及该田地的牛棚最多可以容纳多少牛。
接下来 mm 行，每行三个整数 u, v, wu,v,w，代表存在一条长度为 ww 的连接 uu 和 vv 的道路。
输出格式
输出一行一个整数表示所有奶牛全都躲进牛棚所用的最少时间。如果无法使全部奶牛都躲进牛棚，输出 -1−1。
输入输出样例
输入 #1<button class="copy-btn lfe-form-sz-middle" data-v-370e72e2="" data-v-52f2d52f="" type="button">复制</button>
3 4 7 2 0 4 2 6 1 2 40 3 2 70 2 3 90 1 3 120
输出 #1<button class="copy-btn lfe-form-sz-middle" data-v-370e72e2="" data-v-52f2d52f="" type="button">复制</button> 
View Code
110
思路
这道题和之前EOJ月赛上的一道题差不多。
建图很好想。
对每个 i 点拆开，入点装过路牛，连向S。
出点装雨棚里能待的牛，连向T。
出入点之间的容量显然为雨棚的容量。
用 Floyd 预处理出每个雨棚之间的距离
二分枚举牛进雨棚的时间
以此作为限制条件建图
通过限定连边的长度来限制时间
当恰好流量等于牛的数量时，
说明此时所有牛能进雨棚
注意开 long long
CODE
1 #include <bits/stdc++.h> 2 #define dbg(x) cout << #x << "=" << x << endl 3 #define eps 1e-8 4 #define pi acos(-1.0) 5 6 using namespace std; 7 typedef long long LL; 8 9 const LL inf = 1e13; 10 11 template<class T>inline void read(T &res) 12 { 13 char c;T flag=1; 14 while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0'; 15 while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag; 16 } 17 18 namespace _buff { 19 const size_t BUFF = 1 << 19; 20 char ibuf[BUFF], *ib = ibuf, *ie = ibuf; 21 char getc() { 22 if (ib == ie) { 23 ib = ibuf; 24 ie = ibuf + fread(ibuf, 1, BUFF, stdin); 25 } 26 return ib == ie ? -1 : *ib++; 27 } 28 } 29 30 int qread() { 31 using namespace _buff; 32 int ret = 0; 33 bool pos = true; 34 char c = getc(); 35 for (; (c < '0' || c > '9') && c != '-'; c = getc()) { 36 assert(~c); 37 } 38 if (c == '-') { 39 pos = false; 40 c = getc(); 41 } 42 for (; c >= '0' && c <= '9'; c = getc()) { 43 ret = (ret << 3) + (ret << 1) + (c ^ 48); 44 } 45 return pos ? ret : -ret; 46 } 47 48 const int maxn = 2007; 49 50 int n, m; 51 LL s[maxn], P[maxn]; 52 int S, T; 53 54 struct edge{ 55 int from,to; 56 LL cap,flow; 57 }; 58 59 struct isap 60 { 61 int n,s,t; 62 LL p[maxn],d[maxn],cur[maxn],num[maxn]; 63 vector<int>g[maxn]; 64 vector<edge> edges; 65 void init(int n,int s,int t) { 66 this->n = n; 67 this->s = s; 68 this->t = t; 69 for(int i = 0;i <= 500;i++) g[i].clear(); 70 edges.clear(); 71 memset(p, 0, sizeof(p)); 72 memset(d, 0, sizeof(d)); 73 memset(cur, 0, sizeof(cur)); 74 memset(num, 0, sizeof(num)); 75 } 76 void addegde(int from,int to,int cap) { 77 edges.push_back((edge){from, to, cap, 0}); 78 edges.push_back((edge){to, from, 0, 0}); 79 int m = edges.size(); 80 g[from].push_back(m-2); 81 g[to].push_back(m-1); 82 } 83 84 LL augment() {///找增广路 85 int d = edges.size(); 86 // for ( int i = 0; i < d; ++i ) { 87 // printf("from:%d to:%d cap:%d\n",edges[i].from,edges[i].to,edges[i].cap); 88 // } 89 int x = t; 90 LL a = inf; 91 92 while(x!=s) { 93 a = min(a, edges[p[x]].cap - edges[p[x]].flow); 94 x = edges[p[x]].from; 95 // printf("edges[%d].from:%d\n",p[x], edges[p[x]].from); 96 // printf("x:%d s:%d\n",x, s); 97 } 98 x=t; 99 while(x != s) { 100 edges[p[x]].flow += a; 101 edges[p[x]^1].flow = -a; 102 x = edges[p[x]].from; 103 } 104 return a; 105 } 106 107 LL maxflow() {///更新最大流 108 LL flow = 0; 109 memset(num, 0, sizeof(num)); 110 memset(cur, 0, sizeof(cur)); 111 //memset(d, 0, sizeof(d)); 112 for(int i = 1; i <= n; i++) num[d[i]]++; 113 int x = s; 114 115 //printf("d[%d]:%d\n",s, d[s]); 116 while(d[s] < n) {///最长的一条链上，最大的下标是nv-1，如果大于等于nv说明已断层 117 //printf("d[%d]:%d\n", s, d[s]); 118 if(x == t) { 119 flow += augment(); 120 x = s;//回退 121 } 122 bool ok = 0; 123 for(int i = cur[x]; i < g[x].size(); i++) { 124 edge e = edges[g[x][i]]; 125 //printf("e->to:%d\n",e.to); 126 if(d[x] == d[e.to] + 1 && e.cap > e.flow) { 127 p[e.to] = g[x][i]; 128 cur[x] = i;x = e.to; 129 ok = 1; 130 break; 131 } 132 } 133 if(!ok) { 134 LL m = n-1; 135 for(int i = 0; i < g[x].size();i++) { 136 edge &e=edges[g[x][i]]; 137 if(e.cap>e.flow) m=min(m,d[e.to]); 138 } 139 num[d[x]]--; 140 if(!num[d[x]]) break; 141 d[x] = m+1; 142 num[d[x]]++; 143 cur[x] = 0; 144 if(x != s) x = edges[p[x]].from; 145 } 146 } 147 return flow; 148 } 149 }ISAP; 150 151 LL dis[207][207]; 152 153 inline int id(int a, int b) { 154 return (a - 1) * n + b; 155 } 156 157 bool check(LL x) { 158 ISAP.init(n * 3, 0, n * 2 + 1); 159 for ( int i = 1; i <= n; ++i ) { 160 for ( int j = 1; j <= n; ++j ) { 161 //printf("dis[%d][%d]:%d\n",i, j, dis[i][j]); 162 if(dis[i][j] != inf && dis[i][j] <= x) { 163 ISAP.addegde(i, j + n, inf); 164 //printf("i:%d j+n:%d\n",i, j + n); 165 //ISAP.addegde(j + n, i, 0); 166 } 167 } 168 } 169 int S = 0, T = n * 2 + 1; 170 LL sum = 0; 171 for ( int i = 1; i <= n; ++i ) { 172 ISAP.addegde(S, i, s[i]); 173 sum += s[i]; 174 ISAP.addegde(i + n, T, P[i]); 175 ISAP.addegde(i, i + n, inf); 176 } 177 LL res = ISAP.maxflow(); 178 // dbg(res); 179 // dbg(sum); 180 return res == sum; 181 } 182 183 int main() 184 { 185 //freopen("data.txt", "r", stdin); 186 read(n); read(m); 187 for ( int i = 1; i <= n; ++i ) { 188 read(s[i]); read(P[i]); 189 } 190 for ( int i = 1; i <= n; ++i ) { 191 for ( int j = 1; j <= n; ++j ) { 192 if(i == j) 193 dis[i][j] = dis[j][i] = 0; 194 else { 195 dis[i][j] = dis[j][i] = inf; 196 } 197 } 198 } 199 for ( int i = 1; i <= m; ++i ) { 200 LL u, v, c; 201 read(u); read(v); read(c); 202 if(dis[u][v] == inf || dis[u][v] > c) dis[u][v] = dis[v][u] = c; 203 //ISAP.addegde(u, v, c); 204 } 205 LL l = 0, r = 0, mid; 206 for ( int k = 1; k <= n; ++k ) { 207 for ( int i = 1; i <= n; ++i ) { 208 for ( int j = 1; j <= n; ++j ) { 209 if(i == j) { 210 dis[i][j] = 0; 211 } 212 else { 213 if(dis[i][j] > dis[i][k] + dis[k][j]) { 214 dis[i][j] = dis[i][k] + dis[k][j]; 215 } 216 } 217 r = max(r, dis[i][j]); 218 } 219 } 220 } 221 LL ans = -1; 222 while(l <= r) { 223 mid = (l + r) >> 1; 224 //dbg(mid); 225 if(check(mid)) { 226 ans = mid, r = mid - 1; 227 } 228 else { 229 l = mid + 1; 230 } 231 } 232 cout << ans << endl; 233 return 0; 234 }
#include < bits/stdc++.h >
#define dbg( x ) cout << #x << " = " << x << endl
#define eps 1 e - 8
#define pi acos( - 1.0 )
using namespace std ;
typedef long long LL ;
const LL inf = 1 e 13 ;
template < class T > inline void read(T & res )
{
char c ;T flag = 1 ;
while((c = getchar()) < ' 0 ' ||c > ' 9 ' )if(c == ' - ' )flag =- 1 ;res =c - ' 0 ' ;
while((c = getchar()) >= ' 0 ' &&c <= ' 9 ' )res =res * 10 +c - ' 0 ' ;res *=flag ;
}
namespace _buff {
const size_t BUFF = 1 << 19 ;
char ibuf [BUFF ], *ib = ibuf , *ie = ibuf ;
char getc() {
if (ib == ie ) {
ib = ibuf ;
ie = ibuf + fread(ibuf , 1 , BUFF , stdin );
}
return ib == ie ? - 1 : *ib ++ ;
}
}
int qread() {
using namespace _buff ;
int ret = 0 ;
bool pos = true ;
char c = getc();
for (; (c < ' 0 ' || c > ' 9 ' ) && c != ' - ' ; c = getc()) {
assert( ~c );
}
if (c == ' - ' ) {
pos = false ;
c = getc();
}
for (; c >= ' 0 ' && c <= ' 9 ' ; c = getc()) {
ret = (ret << 3 ) + (ret << 1 ) + (c ^ 48 );
}
return pos ? ret : -ret ;
}
const int maxn = 2007 ;
int n , m ;
LL s [maxn ], P [maxn ];
int S , T ;
struct edge {
int from ,to ;
LL cap ,flow ;
};
struct isap
{
int n ,s ,t ;
LL p [maxn ], d [maxn ], cur [maxn ], num [maxn ];
vector <int> g [maxn ];
vector <edge > edges ;
void init( int n , int s , int t ) {
this -> n = n ;
this -> s = s ;
this -> t = t ;
for( int i = 0 ;i <= 500 ;i ++ ) g [i ].clear();
edges .clear();
memset(p , 0 , sizeof (p ));
memset(d , 0 , sizeof (d ));
memset(cur , 0 , sizeof (cur ));
memset(num , 0 , sizeof (num ));
}
void addegde( int from , int to , int cap ) {
edges .push_back((edge ){from , to , cap , 0} );
edges .push_back((edge ){to , from , 0 , 0} );
int m = edges .size();
g [from ].push_back(m - 2 );
g [to ].push_back(m - 1 );
}
LL augment() { ///找增广路
int d = edges .size();
// for ( int i = 0; i < d; ++i ) {
// printf("from:%d to:%d cap:%d\n",edges[i].from,edges[i].to,edges[i].cap);
// }
int x = t ;
LL a = inf ;
while(x !=s ) {
a = min(a , edges [ p [x ]]. cap - edges [ p [x ]]. flow );
x = edges [ p [x ]]. from ;
// printf("edges[%d].from:%d\n",p[x], edges[p[x]].from);
// printf("x:%d s:%d\n",x, s);
}
x =t ;
while(x != s ) {
edges [ p [x ]]. flow += a ;
edges [ p [x ] ^ 1 ]. flow = -a ;
x = edges [ p [x ]]. from ;
}
return a ;
}
LL maxflow() { ///更新最大流
LL flow = 0 ;
memset(num , 0 , sizeof (num ));
memset(cur , 0 , sizeof (cur ));
//memset(d, 0, sizeof(d));
for( int i = 1 ; i <= n ; i ++ ) num [ d [i ]] ++ ;
int x = s ;
//printf("d[%d]:%d\n",s, d[s]);
while( d [s ] < n ) { ///最长的一条链上，最大的下标是nv-1，如果大于等于nv说明已断层
//printf("d[%d]:%d\n", s, d[s]);
if(x == t ) {
flow += augment();
x = s ; //回退
}
bool ok = 0 ;
for( int i = cur [x ]; i < g [x ].size(); i ++ ) {
edge e = edges [ g [x ][i ]];
//printf("e->to:%d\n",e.to);
if( d [x ] == d [ e . to ] + 1 && e . cap > e . flow ) {
p [ e . to ] = g [x ][i ];
cur [x ] = i ;x = e . to ;
ok = 1 ;
break;
}
}
if( !ok ) {
LL m = n - 1 ;
for( int i = 0 ; i < g [x ].size();i ++ ) {
edge &e = edges [ g [x ][i ]];
if( e . cap > e . flow ) m = min(m , d [ e . to ]);
}
num [ d [x ]] -- ;
if( ! num [ d [x ]]) break;
d [x ] = m + 1 ;
num [ d [x ]] ++ ;
cur [x ] = 0 ;
if(x != s ) x = edges [ p [x ]]. from ;
}
}
return flow ;
}
}ISAP ;
LL dis [ 207 ][ 207 ];
inline int id( int a , int b ) {
return (a - 1 ) * n + b ;
}
bool check(LL x ) {
ISAP .init(n * 3 , 0 , n * 2 + 1 );
for ( int i = 1 ; i <= n ; ++i ) {
for ( int j = 1 ; j <= n ; ++j ) {
//printf("dis[%d][%d]:%d\n",i, j, dis[i][j]);
if( dis [i ][j ] != inf && dis [i ][j ] <= x ) {
ISAP .addegde(i , j + n , inf );
//printf("i:%d j+n:%d\n",i, j + n);
//ISAP.addegde(j + n, i, 0);
}
}
}
int S = 0 , T = n * 2 + 1 ;
LL sum = 0 ;
for ( int i = 1 ; i <= n ; ++i ) {
ISAP .addegde(S , i , s [i ]);
sum += s [i ];
ISAP .addegde(i + n , T , P [i ]);
ISAP .addegde(i , i + n , inf );
}
LL res = ISAP .maxflow();
// dbg(res);
// dbg(sum);
return res == sum ;
}
int main()
{
//freopen("data.txt", "r", stdin);
read(n ); read(m );
for ( int i = 1 ; i <= n ; ++i ) {
read( s [i ]); read( P [i ]);
}
for ( int i = 1 ; i <= n ; ++i ) {
for ( int j = 1 ; j <= n ; ++j ) {
if(i == j )
dis [i ][j ] = dis [j ][i ] = 0 ;
else {
dis [i ][j ] = dis [j ][i ] = inf ;
}
}
}
for ( int i = 1 ; i <= m ; ++i ) {
LL u , v , c ;
read(u ); read(v ); read(c );
if( dis [u ][v ] == inf || dis [u ][v ] > c ) dis [u ][v ] = dis [v ][u ] = c ;
//ISAP.addegde(u, v, c);
}
LL l = 0 , r = 0 , mid ;
for ( int k = 1 ; k <= n ; ++k ) {
for ( int i = 1 ; i <= n ; ++i ) {
for ( int j = 1 ; j <= n ; ++j ) {
if(i == j ) {
dis [i ][j ] = 0 ;
}
else {
if( dis [i ][j ] > dis [i ][k ] + dis [k ][j ]) {
dis [i ][j ] = dis [i ][k ] + dis [k ][j ];
}
}
r = max(r , dis [i ][j ]);
}
}
}
LL ans = - 1 ;
while(l <= r ) {
mid = (l + r ) >> 1 ;
//dbg(mid);
if(check(mid )) {
ans = mid , r = mid - 1 ;
}
else {
l = mid + 1 ;
}
}
cout << ans << endl ;
return 0 ;
}
投递饿了么等公司8个岗位 >