題意：
? ? ? 有n個點，每個點有兩個權值，金子數量還有倉庫容量，金子可以存在自己的倉庫里或者是別的倉庫里，倉庫和倉庫之間有距離，問所有金子都必須存到庫里最大距離的最小是多少？


思路：
? ? ? 比較簡單，方法也不唯一，大體可以這樣，先二分，然后用最大流或者匹配..來判斷是不是滿足就行了，我用的是二分最大流，具體代碼在下面。




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


#define N_node 400 + 50
#define N_edge 200 * 200 * 2 + 10000
#define INF 1000000000


using namespace std;


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


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


typedef struct
{
? ? int x ,t;
}DEP;


STAR E[N_edge];
EDGE edge[N_edge];
DEP xin ,tou;
int list[N_node] ,listt[N_node] ,tot;
int deep[N_node];
int c1[N_node] ,c2[N_node];
int num[N_edge] ,numt[N_edge];




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;
? ? queue<DEP>q;
? ? q.push(xin);
? ? deep[s] = 0;
? ? 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 ++)
? ? listt[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 = listt[s] ;k ;k = E[k].next)
? ? {
? ? ? ? listt[s] = k;
? ? ? ? int c = E[k].cost ,to = E[k].to;
? ? ? ? if(!c || deep[to] != deep[s] + 1)
? ? ? ? continue;
? ? ? ? int tmp = DFS_Flow(to ,t ,minn(c ,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;
}


int GetMaxFlow(int mid ,int n ,int m)
{
? ? memset(list ,0 ,sizeof(list));
? ? tot = 1;
? ? for(int i = 1 ;i <= n ;i ++)
? ? {
? ? ? ? add(0 ,i ,c1[i]);
? ? ? ? add(i ,i + n ,INF);
? ? ? ? add(i + n ,n + n + 1 ,c2[i]);
? ? }


? ? for(int i = 1 ;i <= m ;i ++)
? ? {
? ? ? ? if(edge[i].c <= mid)
? ? ? ? {
? ? ? ? ? ? add(edge[i].a ,edge[i].b + n ,INF);
? ? ? ? ? ? add(edge[i].b ,edge[i].a + n ,INF);
? ? ? ? }
? ? }
? ? return DINIC(0 ,n + n + 1 ,n + n + 1);
}


int main ()
{
? ? int n ,m ,i ,s1 ,s2;
? ? while(~scanf("%d" ,&n) && n)
? ? {
? ? ? ? s1 = s2 = 0;
? ? ? ? for(i = 1 ;i <= n ;i ++)
? ? ? ? {
? ? ? ? ? ? scanf("%d" ,&c1[i]);
? ? ? ? ? ? s1 += c1[i];
? ? ? ? }
? ? ? ? for(i = 1 ;i <= n ;i ++)
? ? ? ? {
? ? ? ? ? ? scanf("%d" ,&c2[i]);
? ? ? ? ? ? s2 += c2[i];
? ? ? ? }
? ? ? ? scanf("%d" ,&m);
? ? ? ? for(i = 1 ;i <= m ;i ++)
? ? ? ? {
? ? ? ? ? ? scanf("%d %d %d" ,&edge[i].a ,&edge[i].b ,&edge[i].c);
? ? ? ? ? ? numt[i] = edge[i].c;
? ? ? ? }


? ? ? ? if(s2 < s1)
? ? ? ? {
? ? ? ? ? ? printf("No Solution\n");
? ? ? ? ? ? continue;
? ? ? ? }


? ? ? ? sort(numt + 1 ,numt + m + 1);
? ? ? ? int numid = 0;
? ? ? ? for(i = 1 ;i <= m ;i ++)
? ? ? ? if(i == 1 || numt[i] != numt[i-1])
? ? ? ? num[++numid] = numt[i];
? ? ? ? num[0] = 0;
? ? ? ? int low = 0 ,up = numid ,mid ,ans = -1;
? ? ? ? while(low <= up)
? ? ? ? {
? ? ? ? ? ? mid = (low + up) >> 1;
? ? ? ? ? ? if(GetMaxFlow(num[mid] ,n ,m) == s1)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? ans = num[mid];
? ? ? ? ? ? ? ? up = mid - 1;
? ? ? ? ? ? }
? ? ? ? ? ? else low = mid + 1;
? ? ? ? }
? ? ? ? if(ans == -1) printf("No Solution\n");
? ? ? ? else printf("%d\n" ,ans);
? ? }
? ? return 0;
}

總結

以上是生活随笔為你收集整理的POJ3228二分最大流的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。