题目：
输入k c m 代表有k台机器 c头牛 每台机器最多服务m头牛
k台机器编号为1～k。c头牛编号为k+1～k+c
下面是一个（k+c）*（k+c）的矩阵
map[i][j]代表从编号为i的实体到编号为j的实体的直接距离
问你要让每头牛都被机器服务 这c头牛中 走的最远距离的最小值（就是说这c头牛每头牛都要走向一个机器，最小化走的最远的那头牛所走的距离）
思路：二分最远的距离mid 如果机器和牛之间的最短距离（最短距离用floyd算法更新即可）小于mid 那么就可以建边（从机器到牛加一条边 权值为1）
然后建立一个超级源点 源点向每台机器建边 权值为m
建立一个超级汇点 每头牛都向汇点建边 权值为1
最后跑最大流 看最大流是否等于c
若等于则还有减小距离的余地 不等于的话就得增大距离了
#include<algorithm> #include<iostream> #include<cstdlib> #include<cstring> #include<cstdio> #include<string> #include<stack> #include<queue> #include<cmath> #include<stack> #include<list> #include<set> typedef long long ll; using namespace std; int k,c,m; int a[233][233];//存矩阵 int num; const int MAXN=233; const int MAXM=40010; const int INF=0x3f3f3f3f; struct Node { int from,to,next; int cap; }edge[MAXM]; int tol; int head[MAXN]; int dep[MAXN]; int gap[MAXN]; void init() { tol=0; memset(head,-1,sizeof(head)); } void addedge(int u,int v,int w) { edge[tol].from=u; edge[tol].to=v; edge[tol].cap=w; edge[tol].next=head[u]; head[u]=tol++; edge[tol].from=v; edge[tol].to=u; edge[tol].cap=0; edge[tol].next=head[v]; head[v]=tol++; } void BFS(int start,int end) { memset(dep,-1,sizeof(dep)); memset(gap,0,sizeof(gap)); gap[0]=1; int que[MAXN]; int front,rear; front=rear=0; dep[end]=0; que[rear++]=end; while(front!=rear) { int u=que[front++]; if(front==MAXN)front=0; for(int i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].to; if(dep[v]!=-1)continue; que[rear++]=v; if(rear==MAXN)rear=0; dep[v]=dep[u]+1; ++gap[dep[v]]; } } } int SAP(int start,int end,int n)//n为节点的个数 包括源点和汇点 { int res=0; BFS(start,end); int cur[MAXN]; int S[MAXN]; int top=0; memcpy(cur,head,sizeof(head)); int u=start; int i; while(dep[start]<n) { if(u==end) { int temp=INF; int inser; for(i=0;i<top;i++) if(temp>edge[S[i]].cap) { temp=edge[S[i]].cap; inser=i; } for(i=0;i<top;i++) { edge[S[i]].cap-=temp; edge[S[i]^1].cap+=temp; } res+=temp; top=inser; u=edge[S[top]].from; } if(u!=end&&gap[dep[u]-1]==0) break; for(i=cur[u];i!=-1;i=edge[i].next) if(edge[i].cap!=0&&dep[u]==dep[edge[i].to]+1) break; if(i!=-1) { cur[u]=i; S[top++]=i; u=edge[i].to; } else { int min=n; for(i=head[u];i!=-1;i=edge[i].next) { if(edge[i].cap==0)continue; if(min>dep[edge[i].to]) { min=dep[edge[i].to]; cur[u]=i; } } --gap[dep[u]]; dep[u]=min+1; ++gap[dep[u]]; if(u!=start)u=edge[S[--top]].from; } } return res; } void floyd() { int j,t,i; for(t=1;t<=num;t++)//一开始这里写成k了 因为开了全局变量k 导致wa.. 编译器会自动覆盖全局变量 但是oj系统不会 { for(i=1;i<=num;i++) { for(j=1;j<=num;j++) { if(a[i][j]>a[i][t]+a[t][j]) { a[i][j]=a[i][t]+a[t][j]; } } } } } void getmap(int mid) { init(); int i,j; for(i=1;i<=k;i++) { for(j=k+1;j<=num;j++) { if(a[i][j]<=mid) { addedge(i, j, 1); } } } for(i=1;i<=k;i++) { addedge(0, i, m); } for(i=k+1;i<=num;i++) { addedge(i,num+1, 1); } } int main() { int i,j; while(scanf("%d%d%d",&k,&c,&m)==3) { num=k+c; int source=0,sink=num+1;//源点与汇点 for(i=1;i<=k+c;i++) { for(j=1;j<=k+c;j++) { scanf("%d",&a[i][j]); if(i!=j&&a[i][j]==0)//这里注意 如果无法到达 说明距离为无穷大而不是0 { a[i][j]=INF; } } } floyd(); int l=0,r=INF; int mid; while(l<=r) { mid=(l+r)/2; getmap(mid);//重新建图 if(SAP(source,sink,num+2)==c) { r=mid-1; } else{ l=mid+1; } } printf("%d\n",l); } return 0; }
