(点击此处查看原题) http://poj.org/problem?id=2112
题目分析
题意: 在一个农场中有 k 台挤奶器和 c 只奶牛, 每个挤奶器最多只能为 m 只奶牛挤奶, 每个挤奶器和奶牛都视为一个点, 将编号 1~k 记为挤奶器的位置, 编号 k+1~k+c 记为奶牛的位置, 奶牛只能在这 k+c 个位置之间移动, 输入将给出每个位置和其余 k+c 个位置的之间道路距离, 其中 0 代表无法到达
问让所有奶牛进行挤奶的情况下 (也就是让每头奶牛都走到一个挤奶器的位置上去, 而且这个挤奶器上的奶牛不得超过 m 个), 求 c 只奶牛中走的最远的奶牛的最小移动总距离.
思路: 首先思考到这题目要二分答案, 因为移动最远的奶牛的移动总距离越大, 就越有可能满足要求
然后我们用 c 次 dijkstra 求出每个奶牛到所有挤奶器的最近距离, 再根据我们二分的奶牛移动最远距离, 限制了每个奶牛可以到达的挤奶器
随后我们就要判断这种情况下是否所有奶牛都可以到达一个挤奶器, 而且每个挤奶器上的奶牛不超过 m 个, 此时就是一个明显的求最大流问题了, 建图如下:
1) 由源点向每个奶牛建一条容量为 1 的边
2) 由每个挤奶器向汇点建一条容量为 m 的边
3) 由每个奶牛向其可以到达的所有挤奶器建一条容量为 inf 的边
最后, 我们跑出这个图的最大流, 如果最大流等于 c, 说明当前的情况是满足的, 需要尝试更小的最远的距离; 如果最大流不等于 c, 说明当前的最远距离太小了, 以至于有奶牛无法到达挤奶器, 需要尝试更大的最远距离.
代码区
- #include<iostream>
- #include<cstdio>
- #include<algorithm>
- #include<cstring>
- #include<queue>
- #include<string>
- #include<fstream>
- #include<vector>
- #include<stack>
- #include <map>
- #include <iomanip>
- #define bug cout <<"**********" << endl
- #define show(x, y) cout<<"["<<x<<","<<y<<"]"
- #define LOCAL = 1;
- using namespace std;
- typedef long long ll;
- const int inf = 0x3f3f3f3f;
- const ll mod = 1e9 + 7;
- const int Max = 1e4 + 10;
- const int Max2 = 3e2+ 10;
- struct Edge // 构建的残余网络
- {
- int to, flow, next;
- } edge[Max << 1];
- struct Edge2 // 原图结点之间的关系
- {
- int to, dis;
- };
- int k, c, m, s, t;
- vector<Edge2> edge_raw[Max2];
- int dist[Max2][Max2]; // 奶牛和机器的最近距离
- bool vis[Max2];
- int head[Max2], tot;
- int dis[Max2], cur[Max2];
- void init()
- {
- memset(dist, inf, sizeof(dist));
- for (int i = 0; i <Max2; i++)
- edge_raw[i].clear();
- }
- void add(int u, int v, int flow)
- {
- edge[tot].to = v;
- edge[tot].flow = flow;
- edge[tot].next = head[u];
- head[u] = tot++;
- }
- void dijkstra(int start)
- {
- memset(vis, 0, sizeof(vis));
- priority_queue<pair<int, int>> q;
- dist[start][start] = 0;
- q.push(make_pair(0, start));
- while (!q.empty())
- {
- int u = q.top().second;
- q.pop();
- if (vis[u])
- continue;
- vis[u] = true;
- for (vector<Edge2>::iterator it = edge_raw[u].begin(); it != edge_raw[u].end(); ++it)
- {
- if (!vis[it->to] && dist[start][it->to]> dist[start][u] + it->dis)
- {
- dist[start][it->to] = dist[start][u] + it->dis;
- q.push(make_pair(-dist[start][it->to], it->to));
- }
- }
- }
- }
- bool bfs() // 判断图是否连通
- {
- queue<int> q;
- memset(dis, -1, sizeof(dis));
- dis[s] = 0;
- q.push(s);
- while (!q.empty())
- {
- int u = q.front();
- q.pop();
- for (int i = head[u]; i != -1; i = edge[i].next)
- {
- int v = edge[i].to;
- if (dis[v] == -1 && edge[i].flow> 0) // 可以借助边 i 到达新的结点
- {
- dis[v] = dis[u] + 1; // 求顶点到源点的距离编号
- q.push(v);
- }
- }
- }
- return dis[t] != -1; // 确认是否连通
- }
- int dfs(int u, int flow_in)
- {
- if (u == t)
- return flow_in;
- int flow_out = 0; // 记录这一点实际流出的流量
- for (int i = cur[u]; i != -1; i = edge[i].next)
- {
- cur[u] = i;
- int v = edge[i].to;
- if (dis[v] == dis[u] + 1 && edge[i].flow> 0)
- {
- int flow_part = dfs(v, min(flow_in, edge[i].flow));
- if (flow_part == 0)
- continue; // 无法形成增广路
- flow_in -= flow_part; // 流出了一部分, 剩余可分配流入就减少了
- flow_out += flow_part; // 记录这一点最大的流出
- edge[i].flow -= flow_part;
- edge[i ^ 1].flow += flow_part; // 减少增广路上边的容量, 增加其反向边的容量
- if (flow_in == 0)
- break;
- }
- }
- return flow_out;
- }
- int Dinic(int ans)
- {
- int sum = 0;
- while (bfs())
- {
- for (int i = 0; i <= ans; i++)
- cur[i] = head[i];
- sum += dfs(s, inf);
- }
- return sum;
- }
- int main()
- {
- #ifdef LOCAL
- //freopen("input.txt", "r", stdin);
- //freopen("output.txt", "w", stdout);
- #endif
- while (scanf("%d%d%d", &k, &c, &m) != EOF)
- {
- init();
- for (int i = 1; i <= k + c; i++)
- {
- for (int j = 1, way; j <= k + c; j++)
- {
- scanf("%d", &way);
- if (way)
- {
- Edge2 e;
- e.to = j;
- e.dis = way;
- edge_raw[i].push_back(e);
- e.to = i;
- edge_raw[j].push_back(e); //POJ 不是 C14 以上的语言, 所以只能写的麻烦一些了
- }
- }
- }
- for (int i = k + 1; i <= k + c; i++) // 求每个奶牛和所有挤奶器的最短距离
- {
- dijkstra(i);
- }
- int l = 1, r = Max, len = 0; // 二分答案
- s = k + c + 1, t = 0; // 源点, 汇点
- while (l <= r)
- {
- memset(head, -1, sizeof(head));
- tot = 0;
- int mid = (l + r)>> 1;
- for (int i = k + 1; i <= k + c; i++)
- {
- for (int j = 1; j <= k; j++)
- {
- if (dist[i][j] <= mid) // 根据限制的最远距离, 选取奶牛可以到达的挤奶器建边
- {
- add(i, j, inf);
- add(j, i, 0);
- }
- }
- add(s, i, 1);
- add(i, s, 0); // 由源点到每头奶牛的边容量均为 1
- }
- for (int i = 1; i <= k; i++)
- {
- add(i, t, m);
- add(t, i, 0); // 由机器到汇点的边容量为机器最大接纳奶牛数
- }
- int max_flow = Dinic(k + c + 1);
- if (max_flow == c) // 满足要求, 进一步缩小最远距离
- {
- r = mid - 1;
- len = mid;
- }
- else
- {
- l = mid + 1;
- }
- }
- printf("%d\n", len);
- }
- return 0;
- }
- View Code
来源: http://www.bubuko.com/infodetail-3164026.html