題意：
? ? ? 有n頭豬，m個豬圈，每個豬圈都有一定的容量（就是最多能裝多少只豬），然后每只豬對每個豬圈的喜好度不同（就是所有豬圈在每個豬心中都有一個排名），然后要求所有的豬都進豬圈，但是要求所有的喜好度排名最低的和最高的差值的絕對值最小，輸出這個最小的差值，就是是每個豬進豬圈后都會產生一個范圍，就是最喜歡和最不喜歡（用排名的名次表示），然后把所有的范圍放在一起，最小的端點個最大的端點的差的絕對值最小是多少？


思路：
? ? ? ?做了將近兩個小時才搞定，一直是超時，先說下我的做法，就是枚舉下界，二分答案，然后DINIC判斷是否可行，用G++交跑100+ms，用C++交超時，還有一個目測比較快的方法，就是把上面的DINIC換成多重匹配，多重匹配處理二分圖的時候比DINIC快，所以理論上更優，可惜我沒寫過多重匹配，這個會的可以試試，最后我用匈牙利，然后暴力拆點去模擬多重匹配，超時了，呵呵，下面是我一開始最笨的方法，枚舉下界+二分答案+DINIC判斷可行性的代碼，還有就是提醒下，輸入的時候那個排名什么的要看清楚，就是讀懂輸入，嘿嘿別的沒啥。




用G++提交
枚舉起點，二分長度，最大流判斷可行。
#include<queue>
#include<stdio.h>
#include<string.h>


#define N_node 1000 + 20 + 5
#define N_edge (1000 * 20 + 1000 + 20) * 2 + 5000
#define INF 1000000000


using namespace std;


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


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


STAR E[N_edge];
DEP xin ,tou;
int list[N_node] ,listt[N_node] ,tot;
int deep[N_node];
int Sort[1005][22];
int Cow[22];
int ANS ,N;




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 = 0;
? ? E[tot].next = list[b];
? ? list[b] = tot;
}


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


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 ++)
? ? listt[i] = list[i];
? ? return deep[t] != -1;
}


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 to = E[k].to;
? ? ? ? int c = E[k].cost;
? ? ? ? if(deep[to] != deep[s] + 1 || !c)
? ? ? ? continue;
? ? ? ? int tmp = DFS_Flow(to ,t, minn(c ,flow - nowflow));
? ? ? ? nowflow += tmp;
? ? ? ? E[k].cost -= tmp;
? ? ? ? E[k^1].cost += tmp;
? ? ? ? if(flow == nowflow)
? ? ? ? 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);
? ? ? ? if(Ans == N) break;
? ? }
? ? return Ans;
}


void Buid(int n ,int m ,int a ,int b)
{
? ? memset(list ,0 ,sizeof(list));
? ? tot = 1;
? ? for(int i = 1 ;i <= n ;i ++)
? ? add(0 ,i ,1);
? ? for(int i = 1 ;i <= m ;i ++)
? ? add(i + n ,m + n + 1 ,Cow[i]);
? ? for(int i = 1 ;i <= n ;i ++)
? ? for(int j = 1 ;j <= m ;j ++)
? ? if(Sort[i][j] >= a && Sort[i][j] <= b)
? ? add(i ,j + n ,1);
}


int solve(int n ,int m ,int ii)
{
? ? int low = 0 ,up = m - ii ,mid ,Ans = INF;
? ? if(up > ANS) up = ANS;
? ? while(low <= up)
? ? {
? ? ? ? mid = (low + up) >> 1;
? ? ? ? Buid(n ,m ,ii ,ii + mid);
? ? ? ? if(DINIC(0 ,n + m + 1 ,n + m + 1) == n)
? ? ? ? {
? ? ? ? ? ? Ans = mid;
? ? ? ? ? ? up = mid - 1;
? ? ? ? }
? ? ? ? else low = mid + 1;
? ? }
? ? return Ans;
}


int main ()
{
? ? int n ,m ,i ,j ,a;
? ? while(~scanf("%d %d" ,&n ,&m))
? ? {
? ? ? ? N = n;
? ? ? ? for(i = 1 ;i <= n ;i ++)
? ? ? ? for(j = 1 ;j <= m ;j ++)
? ? ? ? {
? ? ? ? ? ? scanf("%d" ,&a);
? ? ? ? ? ? Sort[i][a] = j;
? ? ? ? }
? ? ? ? for(i = 1 ;i <= m ;i ++)
? ? ? ? scanf("%d" ,&Cow[i]);
? ? ? ? ANS = INF;
? ? ? ? for(i = 1 ;i <= m ;i ++)
? ? ? ? {
? ? ? ? ? ? ANS = minn(ANS ,solve(n ,m ,i));
? ? ? ? }
? ? ? ? printf("%d\n" ,ANS + 1);
? ? }
? ? return 0;
}

總結

以上是生活随笔為你收集整理的POJ3189二分最大流（枚举下界，二分宽度，最大流判断可行性）的全部內容，希望文章能夠幫你解決所遇到的問題。

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