UVA 10779 Collectors Problem(最大流) - c++编程基础

TOP

UVA 10779 Collectors Problem(最大流)

2014-11-23 20:10:27 来源: 作者: 【大中小】浏览:3次

这个题是很难往网络流上面构思的。。。

从s向每个物品增加容量为Bob拥有数的弧，然后从每个物品向t增加容量为1的弧（代表种类个数）。这时候跑最大流的话，得到的肯定是Bob拥有的初始种类数。那么交换后的最大数呢？

对于Bob以外的小伙伴，如果i拥有j物品超过1个（交换后他自己至少保留一个），从人节点i向物品节点j增加容量为num-1的弧，表示他能输出多少物品，而如果i没有j物品，那么从物品节点j向人节点i增加容量为1的弧（他最多接受1单位的物品）。然后跑最大流得到的就是答案了。

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define FF(i, a, b) for(int i=a; i=b; i--)
#define REP(i, n) for(int i=0; i edges;
vector G[maxn];

void init()
{
    s = 0, t = n + m + 1;   CLR(num, 0);
    REP(i, t+1) G[i].clear();   edges.clear();
}

void add(int from, int to, int cap)
{
    edges.PB((Edge){from, to, cap, 0});
    edges.PB((Edge){to, from, 0, 0});
    int nc = edges.size();
    G[from].PB(nc-2); G[to].PB(nc-1);
}

bool bfs()
{
    CLR(vis, 0);
    queue q;   q.push(s);
    d[s] = 0, vis[s] = 1;
    while(!q.empty())
    {
        int x = q.front(); q.pop();
        int nc = G[x].size();
        REP(i, nc)
        {
            Edge e = edges[G[x][i]];
            if(!vis[e.to] && e.cap > e.flow)
            {
                vis[e.to] = 1;
                d[e.to] = d[x] + 1;
                q.push(e.to);
            }
        }
    }
    return vis[t];
}

int dfs(int x, int a)
{
    if(x == t || a == 0) return a;
    int flow = 0, f, nc = G[x].size();
    for(int& i = cur[x]; i 0)
        {
            e.flow += f;
            edges[G[x][i]^1].flow -= f;
            flow += f;
            a -= f;
            if(a == 0) break;
        }
    }
    return flow;
}

int max_flow()
{
    int flow = 0;
    while(bfs())
    {
        CLR(cur, 0);
        flow += dfs(s, INF);
    }
    return flow;
}

int main()
{
    int T; scanf("%d", &T);
    FF(kase, 1, T+1)
    {
        scanf("%d%d", &n, &m);
        init();
        int x;
        REP(i, n)
        {
            scanf("%d", &num[i][0]);
            while(num[i][0]--)
            {
                scanf("%d", &x);
                num[i][x]++;
            }
        }
        FF(i, 1, m+1)
        {
            if(num[0][i]) add(s, i+n, num[0][i]);
            add(i+n, t, 1);
        }
        FF(i, 1, n)
        {
            FF(j, 1, m+1)
            {
                if(num[i][j] > 1) add(i, j+n, num[i][j] - 1);
                if(num[i][j] == 0) add(j+n, i, 1);
            }
        }
        printf("Case #%d: %d\n", kase, max_flow());
    }
    return 0;
}


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：hdu 1385 Minimum Transport Cost..	下一篇：poj2635

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: