按图论列表上来说是基础题。
这道题是省赛之前过的，现在想再拿出来总结一下，感觉这个类型的题很经典。
题意不叙述了，就是有奶牛和机器，每台奶牛分配一个机器，
牛与牛、牛与机器、机器与机器之间都有一距离，求分配后的最大距离的最小值。
一开始没明白啥叫“最大距离的最小值”，就是C头奶牛、K个挤奶器，C头奶牛若想到全部的挤奶器那里去需要一定的距离，
C头奶牛当中某一头奶牛需要走的距离最大那这个距离便为最大值，要使这个最大值最小。(DT的题意)
这样子二分就好了，(又是二分，泥垢了)，若根据mid建图后的最大流>=C,那这个便是成功的。
有一堆点位于X，一堆点位于Y，若试着建立从X到Y的某种关系，（比如距离、权值），加入超级源点与汇点S、T并建立相应权的边后
肯定能够使得X的点和Y的点分别属于集合S、T(这也是最小割的思想)。
ps:二分输出的技巧如我的代码 if(ans>=mid) R = mid; cout<
废话了比较多，仅是自己身为一个弱渣的小提醒。附个代码。
#include
#include
#include
#include
#include
#include
using namespace std; const int INF = 0x3c3c3c3c; const int maxn = 500 + 10; //结点最多数目 struct Edge{ //代表一条from->to容量为cap,流量为flow的弧 int from, to, cap, flow; }; struct Dinic{ int n, m, s, t; //结点数，边数(包括反向弧), 源点、汇点号 vector
edges; //边表 edge[e]与edge[e^1]互为反向弧 vector
G[maxn]; bool vis[maxn]; int d[maxn]; int cur[maxn]; void AddEdge(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); } bool BFS(){ memset(vis, 0, sizeof(vis)); queue
Q; Q.push(s); d[s] = 0; vis[s] = 1; while(!Q.empty()){ int x = Q.front(); Q.pop(); for(int i = 0;i < G[x].size();i++){ Edge& e = edges[G[x][i]]; if(!vis[e.to] && e.cap>e.flow){ vis[e.to] = 1; d[e.to] = d[x] + 1; Q.push(e.to); } } } return vis[t]; } int DFS(int x, int a){ if(x==t || a==0) return a; int flow = 0, f; for(int &i = cur[x];i < G[x].size();i++){ Edge& e = edges[G[x][i]]; if(d[x]+1==d[e.to] && (f=DFS(e.to, min(a, e.cap-e.flow)))>0){ e.flow += f; edges[G[x][i]^1].flow -= f; flow += f; a -= f; if(a == 0) break; } } return flow; } int Maxflow(int s, int t){ this->s = s; this->t = t; int flow = 0; while(BFS()){ memset(cur, 0, sizeof(cur)); flow += DFS(s, INF); } return flow; } }; int dis[500][500]; int main() { //freopen("in.txt", "r", stdin); int K, C, M; while(scanf("%d %d %d", &K, &C, &M) == 3){ int i, j, k, l, a; int sum = K + C; for(i = 1;i <= sum;i++){ for(j = 1;j <= sum;j++){ scanf("%d", &a); if(i==j) { dis[i][j] = 0; continue; } if(a == 0) dis[i][j] = INF; else dis[i][j] = a; } } for(k = 1;k <= sum;k++){ for(i = 1;i <= sum;i++){ for(j = 1;j <= sum;j++){ if(dis[i][j] > dis[i][k]+dis[k][j]) dis[i][j] = dis[i][k] + dis[k][j]; } } } int L = 1, R = 40000; while(L < R){ int mid =(L+R)/2; Dinic test; for(i = 1;i <= K;i++){ for(j = K+1;j <= sum;j++){ if(dis[i][j]<=mid) test.AddEdge(i,j,1); } } for(i = 1;i <= K;i++) test.AddEdge(0,i,M); for(i = K+1;i <= sum;i++) test.AddEdge(i,sum+1,1); int ans = test.Maxflow(0, sum+1); if(ans>=C) { // why bi_search? it's up R = mid; } else L = mid+1; } printf("%d\n", R); } return 0; }