POJ 2112 二分+网络流 - c++编程基础

题意：

K个挤奶器 C头牛每个挤奶器可同时挤C头牛

牛和挤奶器均分散在各个农场

下面给出 [K+C,K+C] 的邻接矩阵。表示任意点间距离（0表示无法到达）

问：距离挤奶器最远的牛的距离（设计一个方案使得所有牛都能到达挤奶器并且使这个距离最小，题目保证有解）

思路：

Floyd求传递闭包。

二分这个距离（在距离内的边都可行），网络流判断是否可行

(XXWG的代码)

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
          #include 
          
            #include 
           
             #include 
            
              #include 
             
               using namespace std; typedef long long ll; const ll inf=100000000000LL; const ll maxn=2000;++++ ll head[maxn],tol,dep[maxn]; struct node { ll from,to,next,cap; node(){}; node(ll from,ll to, ll next,ll cap):from(from),to(to),next(next),cap(cap){} }edge[1000000]; void add(ll u,ll v,ll cap) { edge[tol]=node(u,v,head[u],cap); head[u]=tol++; edge[tol]=node(v,u,head[v],0); head[v]=tol++; } bool bfs(ll s,ll t) { ll que[maxn],front=0,rear=0; memset(dep,-1,sizeof(dep)); dep[s]=0;que[rear++]=s; while(front!=rear) { ll u=que[front++];front%=maxn; for(ll i=head[u];i!=-1;i=edge[i].next) { ll v=edge[i].to; if(edge[i].cap>0&&dep[v]==-1) { dep[v]=dep[u]+1; que[rear++]=v; rear%=maxn; if(v==t)return 1; } } } return 0; } ll dinic(ll s,ll t) { ll res=0; while(bfs(s,t)) { ll Stack[maxn],top,cur[maxn]; memcpy(cur,head,sizeof(head)); top=0; ll u=s; while(1) { if(t==u) { ll min=inf; ll loc; for(ll i=0;i
              
               edge[Stack[i]].cap) { min=edge[Stack[i]].cap; loc=i; } for(ll i=0;i
               
                0)break; if(cur[u]!=-1) { Stack[top++]=cur[u]; u=edge[cur[u]].to; } else { if(top==0)break; dep[u]=-1; u=edge[Stack[--top]].from; } } } return res; } ll dist[1000][1000]; int main() { int K,C,M,i,j,k,m,n; while(cin>>K>>C>>M) { for(i=1;i<=K+C;i++) for(j=1;j<=K+C;j++) {scanf("%I64d",&dist[i][j]); if(dist[i][j] == 0)dist[i][j] = inf;} for(k=1;k<=K+C;k++) for(i=1;i<=K+C;i++) if(k!=i&&dist[i][k]!=inf) for(j=1;j<=K+C;j++) if(i!=j && j!=k && dist[k][j]!=inf) dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j]); for(i=1;i<=K+C;i++)dist[i][i] = 0; ll left=0,right=30000, ans=inf; while(left<=right) { ll mid=(left+right)>>1; memset(head,-1,sizeof(head));tol=0; for(i=1;i<=K;i++) { for(j=K+1;j<=K+C;j++)if(dist[i][j]<=mid) add(i,j,1); } for(i=K+1;i<=K+C;i++) add(i,K+C+1,1); for(i=1;i<=K;i++) add(0,i,M); if(dinic(0,K+C+1) == C)right=mid-1, ans = min(ans, mid); else left=mid+1; } printf("%I64d\n", ans); } return 0; } /* 2 3 2 0 3 2 1 1 3 0 3 2 0 2 3 0 1 0 1 2 1 0 2 1 0 0 2 0 */