poj2112——Optimal Milking

44424742

最初的想法是二分搜索+二分匹配。
wa了之后，才知道正解应该是：最短路径+二分搜索+多重匹配。
对二分匹配的理解又加深一步。
二分搜索答案，可行性判断的时候，搜索范围应该是左开右闭区间（就是right保证可行，而left-1保证不可行。。。来源：http://hi.baidu.com/forsona/blog/item/f46ed0618b9a4dd78db10dff.html
#include<iostream>#include<cstdio>#include<cstring>using namespace std;#define maxn 250#define maxcost 1e8int g[maxn][maxn];int map[maxn][maxn],maxlen;int k,c,m;bool vis[35];int my[35][35];void init(){int i,j;cin>>k>>c>>m;for(i=1;i<=k+c;i++)for(j=1;j<=k+c;j++){scanf("%d",&g[i][j]);if(g[i][j]==0)g[i][j]=maxcost;}}void Floyd(){int i,j,v,sumn=k+c;for(v=1;v<=sumn;v++)for(i=1;i<=sumn;i++)for(j=1;j<=sumn;j++)if(g[i][j]>g[i][v]+g[v][j])g[i][j]=g[i][v]+g[v][j];}bool find(int p,int mid){int i,j;for(i=1;i<=k;i++){if(vis[i]&&map[p][i]&&map[p][i]<=mid){vis[i]=false;if(my[i][0]<m)//判断容量{my[i][++my[i][0]]=p;return true;}else {for(j=1;j<=my[i][0];j++)if(find(my[i][j],mid)){my[i][j]=p;return true;}}}}return false;}bool match(int mid)//多重匹配{int i;for(i=1;i<=k;i++)my[i][0]=0;for(i=1;i<=c;i++){memset(vis,true,sizeof(vis));if(!find(i,mid)) return false;}return true;}void solve(){int mid;int left=0,right=maxlen;while(left<right){mid=(left+right)>>1;if(match(mid))right=mid;else left=mid+1;}printf("%d\n",right);}void create(){int i,j;maxlen=-1;for(i=1+k;i<=c+k;i++)for(j=1;j<=k;j++){map[i-k][j]=g[i][j];if(map[i-k][j]>maxlen)  maxlen=map[i-k][j];}}int main(){init();Floyd();create();solve();return 0;}