题意:
k c m 分别代表挤奶机数量，牛数量，和挤奶机容量。
接下来（n=k+c）n*n的矩阵A，代表挤奶机或者牛的距离，如果对角线都为0，如果非对角线没有直接路相连也为0。
1 <= K <= 30 1 <= C <= 200 1 <= M <= 15 0<=Aij<=200
求：在机器不能过载工作的前提下，最远的牛到挤奶机的距离的最小值。
思路：
1.先跑一遍FLOYD求出任何两点的最短路。
2.二分最远的距离，从源点到1到k号点的边容量为m，然后将权重不超过最远距离的边加进图中容量为1，最后将每头牛与汇点连容量为1的边。
3.如果最大流跑出来是牛的数量那么符合条件，注意这种情况是找YES_LEFT的情况。
坑点：
1.第二次被输入数据带有k的题目搞傻逼了，这种经常被用到的循环变量下次一定小心。
2.边权不超过200我tm就直接在1到200之间枚举了...无脑值无限大
致谢：
感谢卿学姐邻接表版的当前弧优化的dinic模板。
#include<stdio.h> #include<string.h> #include<algorithm> #include<string.h> #define MAXN 500 #define MAXM 50000 using namespace std; const int inf=0x3f3f3f3f; struct Edge { int v,c,f,nx; Edge() {} Edge(int v,int c,int f,int nx):v(v),c(c),f(f),nx(nx) {} } E[MAXM]; int G[MAXN],cur[MAXN],pre[MAXN],dis[MAXN],gap[MAXN],sz; void init() { sz=0; memset(G,-1,sizeof(G)); } void add_edge(int u,int v,int c) { E[sz]=Edge(v,c,0,G[u]); G[u]=sz++; E[sz]=Edge(u,0,0,G[v]); G[v]=sz++; } bool bfs(int S,int T) { static int Q[MAXN]; memset(dis,-1,sizeof(dis)); dis[S]=0; Q[0]=S; for (int h=0,t=1,u,v,it;h<t;++h) { for (u=Q[h],it=G[u];~it;it=E[it].nx) { if (dis[v=E[it].v]==-1&&E[it].c>E[it].f) { dis[v]=dis[u]+1; Q[t++]=v; } } } return dis[T]!=-1; } int dfs(int u,int T,int low) { if (u==T) return low; int ret=0,tmp,v; for (int &it=cur[u];~it&&ret<low;it=E[it].nx) { if (dis[v=E[it].v]==dis[u]+1&&E[it].c>E[it].f) { if (tmp=dfs(v,T,min(low-ret,E[it].c-E[it].f))) { ret+=tmp; E[it].f+=tmp; E[it^1].f-=tmp; } } } if (!ret) dis[u]=-1; return ret; } int dinic(int S,int T) { int maxflow=0,tmp; while (bfs(S,T)) { memcpy(cur,G,sizeof(G)); while (tmp=dfs(S,T,inf)) maxflow+=tmp; } return maxflow; } struct e{ int st,ed,dis; e(){} e(int a,int b,int c){ st=a;ed=b;dis=c; } }; bool cmp(e a,e b){ return a.dis<b.dis; } e eee[100050]; int pho[300][300]; int main() { int k,c,m; scanf("%d%d%d",&k,&c,&m); for(int i=1;i<=k+c;i++){ for(int j=1;j<=k+c;j++){ scanf("%d",&pho[i][j]); if(pho[i][j]==0&&i!=j){ pho[i][j]=inf; } } } for(int kk=1;kk<=k+c;kk++){ for(int i=1;i<=k+c;i++){ for(int j=1;j<=k+c;j++){ if(pho[i][j]>pho[i][kk]+pho[kk][j]){ pho[i][j]=pho[i][kk]+pho[kk][j]; } } } } int num=0; for(int i=1;i<=k+c;i++){ for(int j=1;j<=k+c;j++){ eee[num++]=e(i,j,pho[i][j]); } } sort(eee,eee+num,cmp); int tnum=0; int s=0,t=k+c+1; int ans=0; int l=1,r=50000; while(l<=r){ int mid=(l+r)>>1; init(); for(int j=1;j<=k;j++){ add_edge(0,j,m); } for(int j=k+1;j<=k+c;j++){ add_edge(j,t,1); } tnum=0; while(tnum<num&&eee[tnum].dis<=mid){ if(eee[tnum].st>k&&eee[tnum].ed<=k){ add_edge(eee[tnum].ed,eee[tnum].st,1); } tnum++; } if(dinic(s,t)>=c)r=mid-1; else l=mid+1; } printf("%d ",l); }