【UVALive 3231】Fair Share 最大流

据说这个问题叫公平分配问题,把M个任务分配给N个处理器,每个任务有两个对应的处理器,可以任选一个处理器处理这个任务,要求所有的处理器中处理任务最多的处理任务尽量少。
Vjudge

题目,不难,一看就是二分时间,然后判断能否在时间之内完成任务,设置0为超级源,N+M+1为超级汇,然后从超级源到每个任务连接一个容量为1的弧,从每个任务连接一个容量为1的弧到处理器,然后从每个处理器到超级汇连接一个容量为MID的弧。然后用Dinic跑最大流。。。。
恩,还好大概一两个小时就打完了,还算满意。但是交上去TLE,于是我郁闷了。调试半天,看了一下刘汝佳的蓝书发现他的DINIC多了个cur数组。。奇奇怪怪的,不知道干嘛,他说避免重复计算。后来在我的代码加上这句话就AC了。

当前弧优化

这个数组cur【u】叫做当前需要搜索的弧的编号,在初始化的时候就是head【u】,但是在后面我一次一次搜索的时候因为我有一部分弧已经没塞满,在我后面搜索的时候就不用考虑,而直接从没有塞满的开始考虑,这是为什么呢?因为我DINIC是在层次图上一条一条的灌水,那么我编号变化只有一种情况就是上一条弧已经被塞满,所以我在循环的时候就可以不断更新cur数组,这样极大的优化了代码吧?反正一加这个就AC了。

代码:

#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>

const int MAXN = 20000;

using namespace std;

int T,N,M,e = 2,sum,ans;
int cur[MAXN],head[MAXN],d[MAXN];

queue<int>q;

struct node{
    int v,c,f,next;
}edge[MAXN*100];

struct node_A{
    int A,B;
}Ta[MAXN];

inline int read()
{
    int x = 0;char ch = getchar();
    while(ch < '0' || '9' < ch){ch = getchar();}
    while('0' <= ch&&ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}
    return x;
}

inline void addedge(int u,int v,int c,int f){
    edge[e] = (node){v,c,f,head[u]};head[u] = e++;
    edge[e] = (node){u,0,f,head[v]};head[v] = e++;
}

inline void build(int MID){
    memset(head,0,sizeof(head));
    e = 2;
    for(int i = 1;i <= M;i++)    //从超级源到每个任务 
        addedge(0,i,1,0);
    for(int i = 1;i <= M;i++)    //从每个任务到对应处理器 
        addedge(i,Ta[i].A+M,1,0),
        addedge(i,Ta[i].B+M,1,0);    
    for(int i = 1;i <= N;i++)    //从每个处理器到超级汇 
        addedge(i+M,M+N+1,MID,0);
}

inline bool bfs()
{
    memset(d,0,sizeof(d));
    q.push(0);d[0] = 1;
    while(!q.empty()){
        int x = q.front();q.pop();
        for(int i = head[x];i;i = edge[i].next){
            int v = edge[i].v;
            if(!d[v] && edge[i].c > edge[i].f){
                d[v] = d[x] + 1;
                q.push(v);
            } 
        }
    }
    return d[M+N+1] ? true : false;
}
int Dinic(int x,int a){
    if(x == N+M+1 || a == 0) return a;
    int flow = 0,f;
    for(int &i = cur[x];i;i = edge[i].next){
        int v = edge[i].v,c = edge[i].c,f = edge[i].f;
        if(d[v] == d[x] + 1 && (f = Dinic(v,min(a,c-f)) > 0)){
            edge[i].f += f;
            edge[i^1].f -= f;
            flow += f;
            a -= f;
            if(a == 0) break;    
        }
    }
    return flow;
}

int main()
{
    T = read();
    while(T--){
        N = read();M = read();    //N是处理器    M是任务    
        
        for(int i = 1;i <= M;i++)    
        Ta[i].A = read(),Ta[i].B = read();
        
        int L = 1,R = M;    
        ans = 0;
        while(L <= R)
        {
            int MID = (L + R) >> 1;
            sum = 0;build(MID);
            while(bfs()){
                for(int i = 0;i <= N+M+1;i++) cur[i] = head[i];
                sum += Dinic(0,100000);
            }
            if(sum >= M) R = MID - 1,ans = MID;
            else L = MID + 1;
        }
        printf("%d\n",ans);
    }
    return 0; 
} 
Last modification:October 1st, 2018 at 08:06 am
If you think my article is useful to you, please feel free to appreciate

Leave a Comment