显然是一个Dinic模板题… 实在不好意思，发博客的时候已经忘了题了…好久之前A的题了 大概思路是floyed跑一遍，然后二分答案，每次在答案之内的就建边，然后跑dinic求最大流，与答案比较即可
1A代码
#include<cstdio> #include<cstring> #include<iostream> #include<queue> #define MAXN 300+10 #define inf 0x7ffffff using namespace std; int K,C,M,n; struct Line{ int to,cost,nxt; }line[MAXN*MAXN]; int head[MAXN],tail,level[MAXN*MAXN]; int G[MAXN][MAXN]; int cnt,s,t; void add_line(int from,int to,int fee){ line[tail].to=to; line[tail].nxt=head[from]; head[from]=tail; line[tail].cost=fee; tail++; } int floyed(){ int maxn=-1; for(int k=1;k<=n;k++){ for(int i=1;i<=n;i++){ if(G[i][k]==inf) continue; for(int j=1;j<=n;j++){ if(G[k][j]!=inf&&G[i][j]>G[i][k]+G[k][j]){ G[i][j]=G[i][k]+G[k][j]; maxn=max(maxn,G[i][j]); } } } } return maxn; } void build(int x){ memset(head,0,sizeof(head)); cnt=0,tail=0; for(int i=1;i<=K;i++){ add_line(i,n+1,M); add_line(n+1,i,0); } for(int i=K+1;i<=n;i++){ add_line(0,i,1); add_line(i,0,0); } for(int i=K+1;i<=n;i++){ for(int j=1;j<=K;j++){ if(G[i][j]<=x){ add_line(i,j,1); add_line(j,i,0); } } } } bool bfs(){ memset(level,0xff,sizeof(level)); queue<int>q; q.push(s); level[s]=0; while(!q.empty()){ int u=q.front();q.pop(); for(int i=head[u];i;i=line[i].nxt){ int v=line[i].to; if(level[v]==-1&&line[i].cost>0){ level[v]=level[u]+1; q.push(v); } } } if(level[t]==-1) return false; return true; } int dfs(int u,int maxflow){ if(u==t) return maxflow; for(int i=head[u];i;i=line[i].nxt){ int v=line[i].to; if(level[v]==level[u]+1&&line[i].cost>0){ int flow=dfs(v,min(line[i].cost,maxflow)); if(flow>0){ line[i].cost-=flow; line[i^1].cost+=flow; return flow; } } } return 0; } int main(){ scanf("%d%d%d",&K,&C,&M); n=K+C; s=0;t=n+1; for(register int i=1;i<=n;i++){ for(register int j=1;j<=n;j++){ scanf("%d",&G[i][j]); if(!G[i][j])G[i][j]=inf; } } int l=0,r=floyed(); while(l<r){ int mid=l+r>>1; build(mid); while(bfs()) cnt+=dfs(s,inf); if(cnt>=C) r=mid; else l=mid+1; } printf("%d",l); return 0; }