/*昨晚寫把Dinic寫錯了，一直不出結果，也沒調出來，睡覺之前猛然想起來，少了
一個break，造成死循環(huán)了。今天把那地方改過來，交上去WA。然后又重新敲之，TLE。
后來檢查了一遍，發(fā)現(xiàn)是Floyd寫錯了，改過后終于過了，發(fā)現(xiàn)網(wǎng)絡流太容易錯了。

　　思路：

1、用Floyd把每個奶牛到每個擠奶機的距離算出來，然后問題就變成了已知c頭奶牛到
k個擠奶機的距離，求走最遠距離的牛走的路程mindis最小是多少。

2、然后建網(wǎng)絡流模型，每頭奶牛和擠奶機都是一個結點。設一個源點s，s到c頭奶牛
的容量都記為1，k個擠奶機到匯點T的距離都記為m。

3、先假設一個mindis的值，然后當奶牛到擠奶機的距離小于mindis時，奶牛結點到擠
奶機結點的容量為1。

4、用一次Dinic()求出最大流，如果 Dinic() == c,mindis減小重復3步驟，直到找
到最小距離。


My Code:*/

#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>

using namespace std;

const int N = 300;
const int inf = 0x6fffffff;

int map[N][N];
int g[N][N];
int layer[N];
bool vis[N];
int T, n;

bool Layer() {
int i, v;
deque<int> q;
memset(layer, -1, sizeof(layer));
q.push_back(0);
layer[0] = 0;
while(!q.empty()){
v = q.front();
q.pop_front();
for(i = 0; i <= T; i++) {
if(g[v][i] > 0 && layer[i] == -1) {
layer[i] = layer[v] + 1;
if(i == T) {q.clear(); return true;}
else q.push_back(i);
}
}
}
return false;
}

int Dinic() {

deque<int> q;
int v, i, vs, ve, min, min_s, sum = 0;
while(Layer()) {
memset(vis, false, sizeof(vis));
vis[0] = true;
q.push_back(0);
while(!q.empty()) {
v = q.back();
if(v == T) {
min = inf;
for(i = 1; i < q.size(); i++) {
vs = q[i-1]; ve = q[i];
if(g[vs][ve] > 0 && min > g[vs][ve]) {
min = g[vs][ve];
min_s = vs;
}
}
sum += min;
for(i = 1; i < q.size(); i++) {
vs = q[i-1]; ve = q[i];
if(g[vs][ve] > 0) {
g[vs][ve] -= min;
g[ve][vs] += min;
}
}
while(!q.empty() && q.back() != min_s) {
vis[q.back()] = false;
q.pop_back();
}
} else {
for(i = 0; i <= T; i++) {
if(g[v][i] > 0 && !vis[i] && layer[i] == layer[v] + 1) {
vis[i] = true;
q.push_back(i);
break;
}
}
if(i > T) q.pop_back();
}
}
}
return sum;
}

void built(int dis, int k, int m) {
int i, j;
memset(g, 0, sizeof(g));
for(i = k+1; i <= n; i++) {
g[0][i] = 1;
for(j = 1; j <= k; j++) {
if(map[i][j] <= dis) g[i][j] = 1;
}
}
for(i = 1; i <= k; i++) {
g[i][T] = m;
}
}

void Floyd() {
int i, j, k;
for(k = 1; k <= n; k++) {
for(i = 1; i <= n; i++) {
for(j = 1; j <= n; j++) {
if(i != j && map[i][k] != inf && map[k][j] != inf && map[i][k] + map[k][j] < map[i][j]){
map[i][j] = map[i][k] + map[k][j];
}
}
}
}
}

int main() {
//freopen("data.in", "r", stdin);

int k, c, m, i, j, ans;
int l, r, mid;

scanf("%d%d%d", &k, &c, &m);{
n = k + c; T = n + 1;
memset(map, 0, sizeof(map));

for(i = 1; i <= n; i++) {
for(j = 1; j <= n; j++) {
scanf("%d", &map[i][j]);
if(map[i][j] == 0) map[i][j] = inf;
}
}
Floyd();
l = 0, r = inf - 10;
while(l < r) {
mid = (l + r) >> 1;

built(mid, k, m);
ans = Dinic();
//printf("%d %d\n", ans, mid);
if(ans == c) r = mid;
else l = mid + 1;
}
printf("%d\n", r);
}
return 0;
}

總結

以上是生活随笔為你收集整理的POJ_2112 Optimal Milking(网络流)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。