poj 2391 Ombrophobic Bovines 二分+拆点建图+最大流 - c++编程基础

顶点具有容量限制的网络流，建图时可以将点x拆成2个点，a,b,将从x进入的点改成从a进入，从x出去的点改成从b出，然后ab之间连一条INF容量的边，这样就可以直接利用网络流模板了。

利用上述建图方法，创建超级源点和超级汇点，二分答案，用最大流判断是否可行。

个人觉得这题最坑的地方就在于数据非常大，爆int，建议初始化时，二分上限<地图上限。

#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
         #include
         
           #include
          
            #include
           
             #define eps 1e-12 #define INF 0x7fffffff #define fuck 0x7fffffffffffffLL #define maxn 3000 using namespace std; int n,m; int en; int st,ed; //源点和汇点 int dis[maxn] ;//dis[i],表示 到 原点 s 的 层数 int que[9999999]; struct edge { int to,c,next; }; edge e[9999999]; int head[maxn]; void add(int a,int b,int c) { e[en].to=b; e[en].c=c; e[en].next=head[a]; head[a]=en++; e[en].to=a; e[en].c=0; e[en].next=head[b]; head[b]=en++; } int bfs() { memset(dis,-1,sizeof(dis)); dis[st]=0; int front=0,rear=0; que[rear++]=st; while(front
            
             >1; build(mid); int tmp=dinic(); if(tmp==sum) {ans=mid;r=mid-1;} else l=mid+1; } return ans; } int main() { while(scanf("%d%d",&n,&m)!=EOF) { input(); cout<