POJ 2112 最大流 最短路

POJ 2112 最大流 最短路
题意:给定K个挤奶器和C头奶牛，每个挤奶器每天最多挤m头奶牛；挤奶器和奶牛称为“实物”，再给每个实物之间的距离。问挤完所有奶牛，奶牛所需走最短的距离。
分析：用Floyd求出“实物”之间的最短距离，求最大流，二分找最短距离。

#include <queue>
#include <cstring>
#include <cstdio>
using namespace std;
const int N = 250;
int K, C, n, m, cnt, st, ed;
struct node{int v, w, nxt;
}edge[N * N];
int e[N][N], fir[N], deep[N];
inline void add(int u, int v, int w){edge[++cnt] = (node){v, w, fir[u]}; fir[u] = cnt;edge[++cnt] = (node){u, 0, fir[v]}; fir[v] = cnt;
}
inline int bfs(){memset(deep, 0, sizeof(deep));deep[st] = 1;queue<int> q;q.push(st);while(!q.empty()){int u = q.front();q.pop();for(int i = fir[u]; i; i = edge[i].nxt){int v = edge[i].v;if(edge[i].w && !deep[v]){deep[v] = deep[u] + 1;q.push(v);}}}return deep[ed];
}
inline int dfs(int u, int fl){if(u == ed || fl == 0) return fl;int f = 0;for(int i = fir[u]; i; i = edge[i].nxt){int v = edge[i].v;if(edge[i].w && deep[u] + 1 == deep[v]){int x = dfs(v, min(fl, edge[i].w));edge[i].w -= x;edge[i^1].w += x;fl -= x;f += x;}}if(!f) deep[u] = -2;return f;
}
inline int Dinic(){int ans = 0, d;while(bfs()){while((d = dfs(st, 0x3f3f3f3f))){ans += d;}}return ans;
}
inline void Floyd(){for(int k = 1; k <= n; k++){for(int i = 1; i <= n; i++){for(int j = 1; j <= n; j++){if(e[i][j] > e[k][i] + e[j][k]){e[i][j] = e[k][i] + e[j][k];}}}}
}
inline void built(int mid){cnt = 1;memset(fir, 0, sizeof(fir));for(int i = K + 1; i <= n; i++) add(st, i, 1);//源点到每个奶牛for(int i = 1; i <= K; i++) add(i, ed, m);//挤奶器到汇点for(int i = 1; i <= K; i++){for(int j = K + 1; j <= n; j++){if(e[i][j] <= mid) add(j, i, 1);//奶牛到挤奶器的距离小于mid，就加一条容量为1的边。}}
}
int main(){
#ifdef ONLINE_JUDGE
#elsefreopen("in.txt", "r", stdin);
#endif //ONLINE_JUDGEwhile(~scanf("%d%d%d", &K, &C, &m)){n = K + C;for(int i = 1; i <= n; i++){for(int j = 1; j <= n; j++){scanf("%d", &e[i][j]);if(i != j && !e[i][j]) e[i][j] = 0x3f3f3f3f;}}Floyd();int l = 0, r = 0x3f3f3f3f;st = 0, ed = n + 1;while(l <= r){int mid = (l + r) / 2;built(mid);int ans = Dinic();if(ans == C) r = mid - 1;//如果满足就缩小上限else l = mid + 1;}printf("%d\n", r + 1);}return 0;
}