Optimal Milking

floyd+多重匹配+二分

先使用floyd求得最短距离
我们二分答案，然后跑多重匹配就好了。

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int max_n = 300;
const int max_m = 1e5;
const int inf = 1e9;
int k,c,m;
int g[max_n][max_n];
struct edge{
    int to,next;
}E[max_m<<1];
int head[max_n];
int cnt=1;
void add(int from,int to){
    E[cnt].to=to;
    E[cnt].next=head[from];
    head[from]=cnt++;
}

bool vis[max_n];
vector<int> match[max_n];
bool matchpath(int u,int mid){
    for (int i=1;i<=k;++i){
        if (!vis[i]&&g[u][i]<=mid){
            vis[i]=1;
            if (match[i].size()<m){
                match[i].push_back(u);
                return true;
            }
            else {
                for (int j=0;j<match[i].size();++j){
                    if (matchpath(match[i][j],mid)){
                        match[i][j]=u;
                        return true;
                    }
                }
            }
        }
    }return false;
}
int Hun(int mid){
    int ans=0;
    for (int i=0;i<=c+k;++i)match[i].clear();
    for (int i=k+1;i<=c+k;++i){
        fill(vis,vis+k+1,0);
        if (matchpath(i,mid))
            ++ans;
    }return ans;
}
bool check(int mid){
    return Hun(mid)==c;
}
int binary(){
    int lft = 0;int rgt=inf;
    while (lft<rgt){
        int mid = (lft+rgt)>>1;
        if (check(mid))rgt=mid;
        else lft=mid+1;
    }return rgt;
}
int main(){
    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",&g[i][j]);
    if(g[i][j]==0)g[i][j]=inf;
    }
    }
    for (int K=1;K<=k+c;++K)
        for (int i=1;i<=k+c;++i)
            for (int j=1;j<=k+c;++j)
                g[i][j]=min(g[i][j],g[i][K]+g[K][j]);
    printf("%d\n",binary());
}

注意了，上面的代码中inf==1e9而不是2e9这是因为，如果是2e9的话，在弗洛伊德的处理时将会爆int然后给我们一个负数，这是很糟糕的。