poj 3189 Steady Cow Assignment 【最大流】【枚举上下界 判断是否满流】

Farmer John‘s N (1 <= N <= 1000) cows each reside in one of B (1 <= B <= 20) barns which, of course, have limited capacity. Some cows really like their current barn, and some are not so happy. 

FJ would like to rearrange the cows such that the cows are as equally happy as possible, even if that means all the cows hate their assigned barn. 

Each cow gives FJ the order in which she prefers the barns. A cow‘s happiness with a particular assignment is her ranking of her barn. Your job is to find an assignment of cows to barns such that no barn‘s capacity is exceeded and the size of the range (i.e., one more than the positive difference between the the highest-ranked barn chosen and that lowest-ranked barn chosen) of barn rankings the cows give their assigned barns is as small as possible.

Line 1: Two space-separated integers, N and B 

Lines 2..N+1: Each line contains B space-separated integers which are exactly 1..B sorted into some order. The first integer on line i+1 is the number of the cow i‘s top-choice barn, the second integer on that line is the number of the i‘th cow‘s second-choice barn, and so on. 

Line N+2: B space-separated integers, respectively the capacity of the first barn, then the capacity of the second, and so on. The sum of these numbers is guaranteed to be at least N.

Line 1: One integer, the size of the minumum range of barn rankings the cows give their assigned barns, including the endpoints.

6 4
1 2 3 4
2 3 1 4
4 2 3 1
3 1 2 4
1 3 4 2
1 4 2 3
2 1 3 2

2

Explanation of the sample: 

Each cow can be assigned to her first or second choice: barn 1 gets cows 1 and 5, barn 2 gets cow 2, barn 3 gets cow 4, and barn 4 gets cows 3 and 6.

犯二，忘建源点到每头牛的边了。没想到过了测试数据，悲催，WA了一次。

题意：给你N头牛、B个畜栏以及畜栏的容量，又根据喜欢程度给出每头牛心中这B个畜栏的排名。

为了便于理解，举个例子。假如一头牛心中对3个畜栏的排名为——1畜栏、3畜栏、2畜栏。若该牛被分配到畜栏3，它的辛福值为2，若被分配到畜栏1，它的幸福值为3，若被分配到畜栏2，它的辛福值为1。

现在让你找出一种方案使得每头牛都属于一个畜栏，并且所有牛的最大幸福值与最小幸福值的差最小，让你输出这个最小差值 + 1。 题目保证至少会有一种方案使得每头牛属于一个畜栏。

思路：枚举差值，根据该差值所得到的 幸福值的上下界建边。跑最大流，看是否满流。

建图：对当前枚举上下界[L, R]，设置超级源点source，超级汇点sink。

1，source到每头牛建边，容量为1，表示一头牛只能选择一个畜栏；

2，若牛选择畜栏的幸福值在[L, R]区间里面，则该牛向畜栏建边，容量为1；

3，所有畜栏向sink建边，容量为当前畜栏可容纳的牛的数目。

跑最大流，看是否满流即可。

AC代码：

#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
#define MAXN 1500
#define MAXM 50000+10
#define INF 0x3f3f3f3f
using namespace std;
struct Edge
{
    int from, to, cap, flow, next;
};
Edge edge[MAXM], Redge[MAXM];
int head[MAXN], edgenum, Rhead[MAXN], Redgenum;
int dist[MAXN], cur[MAXN];
bool vis[MAXN];
int Map[MAXN][25];
int N, B;
int sink, source;
void init()
{
    edgenum = 0;
    memset(head, -1, sizeof(head));
}
void addEdge(int u, int v, int w)
{
    Edge E1 = {u, v, w, 0, head[u]};
    edge[edgenum] = E1;
    head[u] = edgenum++;
    Edge E2 = {v, u, 0, 0, head[v]};
    edge[edgenum] = E2;
    head[v] = edgenum++;
}
void input()
{
    int a;
    init();source = 0, sink = N+B+1;
    for(int i = 1; i <= N; i++)
    {
        addEdge(source, i, 1);//source 向 每头牛建边
        for(int j = 1; j <= B; j++)
        {
            scanf("%d", &a);
            Map[i][a] = B - j + 1;//记录辛福值 按排名前后递减
        }
    }
    for(int i = 1; i <= B; i++)
    {
        scanf("%d", &a);
        addEdge(i+N, sink, a);//每个畜栏向sink建边
    }
}
void getMap(int L, int R)
{
    for(int i = 1; i <= N; i++)
    {
        for(int j = 1; j <= B; j++)
        {
            if(Map[i][j] >= L && Map[i][j] <= R)//根据上下界 建边
                addEdge(i, j+N, 1);
        }
    }
}
bool BFS(int s, int t)
{
    queue<int> Q;
    memset(dist, -1, sizeof(dist));
    memset(vis, false, sizeof(vis));
    dist[s] = 0;
    vis[s] = true;
    Q.push(s);
    while(!Q.empty())
    {
        int u = Q.front();
        Q.pop();
        for(int i = head[u]; i != -1; i = edge[i].next)
        {
            Edge E = edge[i];
            if(!vis[E.to] && E.cap > E.flow)
            {
                dist[E.to] = dist[u] + 1;
                if(E.to == t) return true;
                vis[E.to] = true;
                Q.push(E.to);
            }
        }
    }
    return false;
}
int DFS(int x, int a, int t)
{
    if(x == t || a == 0) return a;
    int flow = 0, f;
    for(int &i = cur[x]; i != -1; i = edge[i].next)
    {
        Edge &E = edge[i];
        if(dist[E.to] == dist[x] + 1 && (f = DFS(E.to, min(a, E.cap - E.flow), t)) > 0)
        {
            edge[i].flow += f;
            edge[i^1].flow -= f;
            flow += f;
            a -= f;
            if(a == 0) break;
        }
    }
    return flow;
}
int Maxflow(int s, int t)
{
    int flow = 0;
    while(BFS(s, t))
    {
        memcpy(cur, head, sizeof(head));
        flow += DFS(s, INF, t);
    }
    return flow;
}
void solve()
{
    memcpy(Redge, edge, sizeof(edge));
    memcpy(Rhead, head, sizeof(head));
    Redgenum = edgenum;
    bool flag = false;
    int ans;
    for(int i = 0; i < B; i++)//枚举差值
    {
        for(int j = 1; j <= B-i; j++)//枚举下界 最低辛福值
        {
            memcpy(edge, Redge, sizeof(Redge));//copy
            memcpy(head, Rhead, sizeof(Rhead));
            edgenum = Redgenum;
            getMap(j, j + i);
            if(Maxflow(source, sink) == N)//最先找到的 一定最优
            {
                flag = true;
                ans = i;
                break;
            }
        }
        if(flag)
            break;
    }
    printf("%d\n", ans+1);
}
int main()
{
    while(scanf("%d%d", &N, &B) != EOF)
    {
        input();
        solve();
    }
    return 0;
}