POJ2391 Ombrophobic Bovines 二分+最大流+拆点

　　这个题目很容易想到二分求解，我开始没有拆点，wa了很多次！后来发现，如果不拆点，二分枚举答案是没有意义的。因为在网络中，已建立的边可以相互联通，那么它们的距离相加可能会超过二分的限制，导致没有意义。那么我们可以把每个区域拆成两个点，一个在X集合，一个在Y集合，增加一个源点s和汇点t。从s向每个X集合得点建立边，容量为这个区域本原有的奶牛数，从每个Y集合的点建立边，容量为这个区域奶牛数的限制。然后，如果X集合点和Y集合点之间的最短距离小于二分限制的话那就建立边，容量为X集合点的原有的奶牛数。那么最大流就是可容纳的奶牛数量了。这个题目还有些细节问题值得注意，就是ans=-1的情况，还有就是long long的注意。开始这个我没注意好，贡献了很多次wa！

  1 //STATUS:G++_AC_188MS_1628KB
  2  #include<stdio.h>
  3  #include<stdlib.h>
  4  #include<string.h>
  5  #include<math.h>
  6  #include<iostream>
  7  #include<string>
  8  #include<algorithm>
  9  #include<vector>
 10  #include<queue>
 11  #include<stack>
 12  #include<map>
 13  using namespace std;
 14  #define LL __int64
 15  #define Max(a,b) ((a)>(b)?(a):(b))
 16  #define Min(a,b) ((a)<(b)?(a):(b))
 17  #define mem(a,b) memset(a,b,sizeof(a))
 18  #define lson l,mid,rt<<1
 19  #define rson mid+1,r,rt<<1|1
 20  const int MAX=210,INF=0x3f3f3f3f;
 21  const LL LLNF=0x3f3f3f3f3f3f3f3fLL;
 22  
 23  struct Edge{
 24      int u,v,cap;
 25  }e[MAX*MAX*2];
 26  
 27  LL w[MAX][MAX],d[MAX*2];
 28  int first[MAX*2],next[MAX*MAX*2],p[MAX*2];
 29  int wt[MAX][MAX],cur[MAX*2],num[MAX*2],nod[MAX][2],inq[MAX];
 30  int n,m,s,t,mt,tar,hav;
 31  LL maxlen,minlen;
 32  
 33  void adde(int a,int b,int val)
 34  {
 35      e[mt].u=a;e[mt].v=b;
 36      e[mt].cap=val;
 37      next[mt]=first[a];first[a]=mt++;
 38      e[mt].u=b;e[mt].v=a;
 39      e[mt].cap=0;
 40      next[mt]=first[b];first[b]=mt++;
 41  }
 42  
 43  void spfa(int s)
 44  {
 45      int i,x;
 46      queue<int> q;
 47      mem(inq,0);
 48      mem(d,0x3f);
 49      d[s]=0;
 50      q.push(s);
 51      while(!q.empty()){
 52          x=q.front();q.pop();
 53          inq[x]=0;
 54          for(i=1;i<=n;i++){
 55              if(wt[x][i]!=INF && d[x]+wt[x][i]<d[i]){
 56                  d[i]=d[x]+wt[x][i];
 57                  if(!inq[i]){
 58                      inq[i]=1;
 59                      q.push(i);
 60                  }
 61              }
 62          }
 63      }
 64  }
 65  
 66  int augment()
 67  {
 68      int x=t,a=INF;
 69      while(x!=s){
 70          a=Min(a,e[p[x]].cap);
 71          x=e[p[x]].u;
 72      }
 73      x=t;
 74      while(x!=s){
 75          e[p[x]].cap-=a;
 76          e[p[x]^1].cap+=a;
 77          x=e[p[x]].u;
 78      }
 79      return a;
 80  }
 81  
 82  int isap()
 83  {
 84      int i,flow=0,x,ok;
 85      mem(d,0);mem(num,0);
 86      num[0]=t+1;
 87      for(i=0;i<=t;i++)cur[i]=first[i];
 88      x=s;
 89      while(d[s]<=t){
 90          if(x==t){
 91              flow+=augment();
 92              x=s;
 93          }
 94          ok=0;
 95          for(i=cur[x];i!=-1;i=next[i]){
 96              if(e[i].cap && d[x]==d[e[i].v]+1){
 97                  ok=1;
 98                  p[e[i].v]=i;
 99                  cur[x]=i;
100                  x=e[i].v;
101                  break;
102              }
103          }
104          if(!ok){
105              int m=t;
106              for(i=first[x];i!=-1;i=next[i])
107                  if(e[i].cap && d[e[i].v]<m)m=d[e[i].v];
108              if(--num[d[x]]==0)break;
109              num[d[x]=m+1]++;
110              cur[x]=first[x];
111              if(x!=s)x=e[p[x]].u;
112          }
113      }
114      return flow;
115  }
116  
117  LL binary()
118  {
119      int i,j;
120      LL low=minlen-1,high=maxlen+1,mid;
121      while(low<high){
122          mid=(low+high)>>1;
123          mt=0;
124          mem(first,-1);
125          for(i=1;i<=n;i++){
126              if(nod[i][0]){
127                  adde(s,i,nod[i][0]);
128                  for(j=1;j<=n;j++)
129                      if(w[i][j]<=mid)
130                          adde(i,n+j,nod[i][0]);
131              }
132              adde(n+i,t,nod[i][1]);
133          }
134          int tt=isap();
135          if(tt<tar)low=mid+1;
136          else high=mid;
137      }
138      return low==maxlen+1?-1:low;
139  }
140  
141  int main()
142  {
143   //   freopen("in.txt","r",stdin);
144      int i,j,a,b,val;
145      LL ans;
146      while(~scanf("%d%d",&n,&m))
147      {
148          tar=hav=0;
149          s=0;t=2*n+1;
150          maxlen=-LLNF,minlen=LLNF;
151          mem(w,0x3f);
152          mem(wt,0x3f);
153          for(i=1;i<=n;i++){
154              scanf("%d%d",&nod[i][0],&nod[i][1]);
155              tar+=nod[i][0];hav+=nod[i][1];
156          }
157          if(tar<=hav){
158              for(i=0;i<m;i++){
159                  scanf("%d%d%d",&a,&b,&val);
160                  if(val<wt[a][b])wt[a][b]=wt[b][a]=val;
161              }
162              for(i=1;i<=n;i++){
163                  spfa(i);
164                  for(j=1;j<=n;j++){
165                      w[j][i]=d[j];
166                      if(d[j]<minlen && i!=j)minlen=d[j];
167                      if(d[j]>maxlen && d[j]!=LLNF)maxlen=d[j];
168                  }
169              }
170              ans=binary();
171          }
172          else {
173              ans=-1;
174              while(m--)scanf("%d%d%d",&a,&a,&a);
175          }
176  
177          printf("%I64d\n",ans);
178      }
179      return 0;
180  }