poj2112——Optimal Milking
最初的想法是二分搜索+二分匹配。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;int map,maxlen;int k,c,m;bool vis;int my;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);if(g==0)g=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>g+g)g=g+g;}bool find(int p,int mid){int i,j;for(i=1;i<=k;i++){if(vis&&map&&map<=mid){vis=false;if(my<m)//判断容量{my[++my]=p;return true;}else {for(j=1;j<=my;j++)if(find(my,mid)){my=p;return true;}}}}return false;}bool match(int mid)//多重匹配{int i;for(i=1;i<=k;i++)my=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=g;if(map>maxlen)maxlen=map;}}int main(){init();Floyd();create();solve();return 0;}
页:
[1]