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然后给我们一个负数,这是很糟糕的。