poj3189:http://poj.org/problem?id=3189
题意：这一题的题意。我看了很长时间才弄懂。就是给你n头牛，m个牛棚，每个牛对每一个牛棚会有一个满值，第i行第j个数表示的是第i头牛满意度为j的是牛棚mp[i][j],而且牛棚会有一定的容量。然后把牛分配到相应的牛棚，使得最大的满意度和最小的满意度之间的差值最小。
题解：由于，满意度的范围很小，所以就自然想到用枚举区间的办法，枚举满意度，但是如果没有优化的话，是会T的，我加了一个二分以及其他的优化，跑了300多点，
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<queue>
#define INF 100000000
using namespace std;
const int N=;
const int M=;
struct Node{
int v;
int f;
int next;
}edge[M];
int n,m,u,v,cnt,sx,ex;
int head[N],pre[N];
int val[N][],val1[N];//根据题目要求申请
void init(){
cnt=;
memset(head,-,sizeof(head));
}
void add(int u,int v,int w){
edge[cnt].v=v;
edge[cnt].f=w;
edge[cnt].next=head[u];
head[u]=cnt++;
edge[cnt].f=;
edge[cnt].v=u;
edge[cnt].next=head[v];
head[v]=cnt++;
}
bool BFS(){
memset(pre,,sizeof(pre));
pre[sx]=;
queue<int>Q;
Q.push(sx);
while(!Q.empty()){
int d=Q.front();
Q.pop();
for(int i=head[d];i!=-;i=edge[i].next ){
if(edge[i].f&&!pre[edge[i].v]){
pre[edge[i].v]=pre[d]+;
Q.push(edge[i].v);
}
}
}
return pre[ex]>;
}
int dinic(int flow,int ps){
int f=flow;
if(ps==ex)return f;
for(int i=head[ps];i!=-;i=edge[i].next){
if(edge[i].f&&pre[edge[i].v]==pre[ps]+){
int a=edge[i].f;
int t=dinic(min(a,flow),edge[i].v);
edge[i].f-=t;
edge[i^].f+=t;
flow-=t;
if(flow<=)break;
} }
if(f-flow<=)pre[ps]=-;
return f-flow;
}
int solve(){
int sum=;
while(BFS())
sum+=dinic(INF,sx);
return sum;
}
int main(){
int ans,temp;
while(~scanf("%d%d",&n,&m)) {
init();
ans=INF;sx=,ex=n+m+;
for(int i=;i<=n;i++)
for(int j=;j<=m;j++){
scanf("%d",&temp);
val[i][temp]=j;
}
for(int i=;i<=m;i++)
scanf("%d",&val1[i]);
for(int i=;i<=m;i++){
int l=i,r=m;
while(l<=r){
int mid=(l+r)/;
if(mid-i>=ans){
r=mid-;
continue;
}
init();
for(int k=;k<=n;k++)
add(,k,);
for(int k=;k<=n;k++)
for(int h=;h<=m;h++)
if(val[k][h]<=mid&&val[k][h]>=i)
add(k,n+h,);
for(int k=;k<=m;k++)
add(k+n,n+m+,val1[k]);
if(solve()==n){
ans=min(ans,mid-i);
r=mid-;
}
else
l=mid+;
}
}
printf("%d\n",ans+);
}
return ;
}