POJ 3228 二分最大流

题意：
给你N个位置，每个位置都有金矿数量和仓库数量，然后位置和位置之间的距离给了出来，最后问你吧所有的金矿都放到库里面走的路径最长的最短是多少？

思路：
比较简单的一个题，直接二分答案，然后用最大流是否满流来判断二分方向，还有就是建图的时候不用拆点什么的，一开始建图想麻烦了，都快敲完了才反应过来，具体看代码。

#include<stdio.h>
#include<string.h>
#include<queue>

#define N_node 200 + 10
#define N_edge 90000
#define INF 1000000000

using namespace std;

typedef struct
{
int to ,cost ,next;
}STAR;

typedef struct
{
int x ,t;
}DEP;

typedef struct
{
int a ,b ,c;
}EDGE;

EDGE edge[22000];
STAR E[N_edge];
DEP xin ,tou;
int list[N_node] ,list2[N_node] ,tot;
int deep[N_node];
int aaa[220] ,bbb[220];

void add(int a ,int b ,int c)
{
     E[++tot].to = b;
     E[tot].cost = c;
     E[tot].next = list[a];
     list[a] = tot;

     E[++tot].to = a;
     E[tot].cost = c;
     E[tot].next = list[b];
     list[b] = tot;
}

bool BFS_Deep(int s ,int t ,int n)
{
   memset(deep ,255 ,sizeof(deep));
   xin.x = s ,xin.t = 0;
   deep[xin.x] = xin.t;
   queue<DEP>q;
   q.push(xin);
   while(!q.empty())
   {
      tou = q.front();
      q.pop();
      for(int k = list[tou.x] ;k ;k = E[k].next)
      {
          xin.x = E[k].to;
          xin.t = tou.t + 1;
          if(deep[xin.x] != -1 || !E[k].cost)
          continue;
          deep[xin.x] = xin.t;
          q.push(xin);
      }
   }
   for(int i = 0 ;i <= n ;i ++)
   list2[i] = list[i];
   return deep[t] != -1;
}

int minn(int x ,int y)
{
return x < y ? x : y;
}

int DFS_Flow(int s ,int t ,int flow)
{
   if(s == t) return flow;
   int nowflow = 0;
   for(int k = list2[s] ;k ;k = E[k].next)
   {
       list2[s] = k;
       int to = E[k].to;
       if(deep[to] != deep[s] + 1 || !E[k].cost)
       continue;
       int tmp = DFS_Flow(to ,t ,minn(E[k].cost ,flow - nowflow));
       nowflow += tmp;
       E[k].cost -= tmp;
       E[k^1].cost += tmp;
       if(nowflow == flow) break;
   }
   if(!nowflow) deep[s] = 0;
   return nowflow;
}

int DINIC(int s ,int t ,int n)
{
   int Ans = 0;
   while(BFS_Deep(s ,t ,n))
   {
       Ans += DFS_Flow(s ,t ,INF);
   }
   return Ans;
}

bool ok(int n ,int m ,int sum ,int mid)
{
     memset(list ,0 ,sizeof(list)) ,tot = 1;
     for(int i = 1 ;i <= n ;i ++)
     {
        add(0 ,i ,aaa[i]);
        add(i ,n + 1 ,bbb[i]);
     }
     for(int i = 1 ;i <= m ;i ++)
     if(edge[i].c <= mid)
     {
        add(edge[i].a ,edge[i].b ,INF);
     }
     int flow = DINIC(0 ,n + 1 ,n + 1);
     return flow == sum;
}

int main ()
{
    int n ,m ,i ,sum;
    while(~scanf("%d" ,&n) && n)
    {
        for(sum = 0 ,i = 1 ;i <= n ;i ++)
        {
           scanf("%d" ,&aaa[i]);
           sum += aaa[i];
        }
        for(i = 1 ;i <= n ;i ++)
        scanf("%d" ,&bbb[i]);
        scanf("%d" ,&m);
        for(i = 1 ;i <= m ;i ++)
        scanf("%d %d %d" ,&edge[i].a ,&edge[i].b ,&edge[i].c);
        int low ,up ,mid ,Ans = -1;
        low = 0 ,up = 11000;
        while(low <= up)
        {
           mid = (low + up) >> 1;
           if(ok(n ,m ,sum ,mid))
           {
               Ans = mid;
               up = mid - 1;
           }
           else low = mid + 1;
        }
        Ans == -1 ? puts("No Solution"):printf("%d " ,Ans);
    }
    return 0;
}