这本是一个非常简单的问题，然而奶牛们由于下雨已经非常混乱，无法完成这一计算，于是这个任务就交给了你。(奶牛混乱的原因看题目描述)
在一个农场里有 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。
3 4 7 2 0 4 2 6 1 2 40 3 2 70 2 3 90 1 3 120
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 }
原文：https://www.cnblogs.com/orangeko/p/12662566.html
