跟上题一样，因为一开始那份模板用的少，总怀疑那份sap模板出错了，今天换了一个模板做另外一题很像的题。（先前的模板不能处理过大的数）
事实证明我过程中处理错了，好吧，先放着，校赛完在来找错了。
////////////////////////////////////////////
最后在错误在建图的过程中，严格建图过程，因为增加了牛与牛和机器与机器的距离,导致求最大流结果时出错。
代码：
#include<iostream> #include<cstring> #include<cstdio> #define MAXN 405 #define INF 1e8 #define min(a,b) (a<b?a:b) #define max(a,b) (a>b?a:b) using namespace std; struct edge { int u,v,w,next; }E[200000]; int head[MAXN],ecnt; int gap[MAXN],cur[MAXN],pre[MAXN],dis[MAXN]; int map[300][300]; int l,r,mid; int N,M,scr,sink,vn,num; int k,c1,m; void Floyd() { for(int k=1;k<=sink-1;k++) for(int i=1;i<=sink-1;i++) if(i!=k&&map[i][k]!=-1) for(int j=1;j<=sink-1;j++) { if(i!=j&&j!=k&&map[k][j]!=-1) { if(map[i][j]==-1) map[i][j]=map[i][k]+map[k][j]; else map[i][j]=map[i][j]>map[i][k]+map[k][j]?map[i][k]+map[k][j]:map[i][j]; } } } void Insert(int u,int v,int w) { E[ecnt].u=u; E[ecnt].v=v; E[ecnt].w=w; E[ecnt].next=head[u]; head[u]=ecnt++; E[ecnt].u=v; E[ecnt].v=u; E[ecnt].w=0; E[ecnt].next=head[v]; head[v]=ecnt++; } int Sap(int s,int t,int n)//核心代码(模版) {
int ans=0,aug=INF;//aug表示增广路的流量 int i,v,u=pre[s]=s; for(i=0;i<=n;i++) { cur[i]=head[i]; dis[i]=gap[i]=0; } gap[s]=n; bool flag; while(dis[s]<n) { flag=false; for(int &j=cur[u];j!=-1;j=E[j].next)//一定要定义成int &j,why { v=E[j].v; if(E[j].w>0&&dis[u]==dis[v]+1) { flag=true;//找到容许边 aug=min(aug,E[j].w); pre[v]=u; u=v; if(u==t) { ans+=aug; while(u!=s) { u=pre[u]; E[cur[u]].w-=aug; E[cur[u]^1].w+=aug;//注意 } aug=INF; } break;//找到一条就退出 } } if(flag) continue; int mindis=n; for(i=head[u];i!=-1;i=E[i].next) { v=E[i].v; if(E[i].w>0&&dis[v]<mindis) { mindis=dis[v]; cur[u]=i; } } if((--gap[dis[u]])==0) break; gap[dis[u]=mindis+1]++; u=pre[u]; } return ans; } bool judge(int mid) { memset(head,-1,sizeof(head));ecnt=0; for(int i=k+1;i<=k+c1;i++)//源点 { Insert(scr,i,1); } for(int i=1;i<=k;i++)//汇点 { Insert(i,sink,m); } for(int i=k+1;i<=k+c1;i++) for(int j=1;j<=k;j++) if(map[i][j]<=mid&&map[i][j]!=-1) { Insert(i,j,INF); } //cout<<l<<' '<<r<<endl; int ans=Sap(scr,sink,vn);
return ans==c1; } int main() { while(scanf("%d%d%d",&k,&c1,&m)!=EOF) { memset(map,-1,sizeof(map)); for(int i=1;i<=k+c1;i++) { for(int j=1;j<=k+c1;j++) { scanf("%d",&map[i][j]); if(map[i][j]==0&&i!=j) map[i][j]=-1; } }
scr=0;sink=k+c1+1;vn=sink+1; Floyd(); /*for(int i=1;i<=k+c1;i++) { cout<<endl; for(int j=1;j<=k+c1;j++) { cout<<map[i][j]<<' '; } }*/ int tmp=-1; for(int i=1;i<=sink-1;i++) //找最短路的最大值 for(int j=1;j<=sink-1;j++) { if(map[i][j]!=-1&&map[i][j]>tmp) tmp=map[i][j]; } l=0;r=0;mid=0; r=tmp; //cout<<endl<<tmp<<endl; while(l!=r) { mid=(l+r)>>1; if(judge(mid)) //大了 { r=mid; } else l=mid+1; //cout<<l<<' '<<r<<endl; } printf("%d\n",r); } return 0; }