[网络流24题] 试题库问题

摘要:
链接:P2763门户解决方案?

Link:

P2763 传送门

Solution:

吐槽一下数据,说好都是正整数结果发现有0?

此类有容量限制的匹配问题首先要想网络流

建图:$<S,k,x><k,n,1><n,T,1>$

判断能否满流就相当于判断了可行性,输出方案时找$k$当前流量为0的边即可

此题由于要求的类型数可能为0,因此输出时要注意排除起点$S$

Code:

#include <bits/stdc++.h>

using namespace std;
#define X first
#define Y second
typedef pair<int,int> P;
typedef long long ll;
const int MAXN=1e4+10,INF=1<<30;
int n,k,x,num,sum;

namespace Maxflow
{
    struct edge{int nxt,to,cap;}e[MAXN<<2];
    int S,T,head[MAXN],iter[MAXN],dist[MAXN],tot=-1;
    void add_edge(int from,int to,int cap)
    {
        e[++tot].nxt=head[from];e[tot].to=to;e[tot].cap=cap;head[from]=tot;
        e[++tot].nxt=head[to];e[tot].to=from;e[tot].cap=0;head[to]=tot;
    }
    
    bool bfs()
    {
        memset(dist,-1,sizeof(dist));
        queue<int> q;q.push(S);dist[S]=0;
        while(!q.empty())
        {
            int v=q.front();q.pop();
            for(int i=head[v];i!=-1;i=e[i].nxt)
            {
                if(e[i].cap&&dist[e[i].to]==-1)
                    dist[e[i].to]=dist[v]+1,q.push(e[i].to);
            }
        }
        return dist[T]!=-1;
    }
    
    int dfs(int v,int f)
    {
        if(v==T) return f;
        int ret=0;
        for(int &i=iter[v];i!=-1;i=e[i].nxt)
            if(dist[e[i].to]==dist[v]+1&&e[i].cap)
            {
                int d=dfs(e[i].to,min(f,e[i].cap));
                e[i].cap-=d;e[i^1].cap+=d;
                f-=d;ret+=d;if(!f) break;
            }
        return ret;
    }
    
    int Dinic()
    {
        int ret=0;
        while(bfs())
        {
            for(int i=0;i<MAXN;i++) iter[i]=head[i];
            ret+=dfs(S,INF);
        }
        return ret;
    }
}
using namespace Maxflow;

int main()
{
    scanf("%d%d",&k,&n);
    S=0;T=n+k+1;memset(head,-1,sizeof(head));
    for(int i=1;i<=k;i++)
        scanf("%d",&x),add_edge(S,i,x),sum+=x;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&num);
        add_edge(k+i,T,1);
        while(num--)
            scanf("%d",&x),add_edge(x,k+i,1);
    }
    
    int mf=Dinic();
    if(mf!=sum) return puts("No Solution!"),0;
    for(int i=1;i<=k;i++)
    {
        printf("%d: ",i);
        for(int j=head[i];~j;j=e[j].nxt)
            if(!e[j].cap&&e[j].to!=S) printf("%d ",e[j].to-k);
        puts("");
    }
    return 0;
}

免责声明:文章转载自《[网络流24题] 试题库问题》仅用于学习参考。如对内容有疑问,请及时联系本站处理。

上篇[网络流24题] 魔术球问题jQuery常用事件,each循环,引用当前时间下篇

宿迁高防,2C2G15M,22元/月;香港BGP,2C5G5M,25元/月 雨云优惠码:MjYwNzM=

相关文章

BZOJ2055 80人环游世界 网络流 费用流 有源汇有上下界的费用流

https://darkbzoj.cf/problem/2055 https://blog.csdn.net/Clove_unique/article/details/54864211←对有上下界费用流的处理方法 首先建立附加源汇ss,tt对于原图里有的一条边x->y,[l,r],cost,变成x->y,r-l,cost每一个点的权di定义为所...

[网络流]最大流

网络流最大流最小割 题目链接 就是一道点割。 先说边割 边割比较常见。 最大流 最大流等于最小割,我懒得证。 求最大流的思路就是每次尝试找一条从源点到汇点的通路,然后找到这条路上残余流量最小的流量,答案加上这个流量,这条通路上每条边的残余流量减去这个值,反向边加上这个值。 关于反向边,实际上是一个反悔机制。反向流多少,表示正向已经流了多少。也就是说,如果我们...

Libre 6006 「网络流 24 题」试题库 / Luogu 2763 试题库问题 (网络流,最大流)

Libre 6006 「网络流 24 题」试题库 / Luogu 2763 试题库问题 (网络流,最大流) Description 问题描述: 假设一个试题库中有n道试题。每道试题都标明了所属类别。同一道题可能有多个类别属性。现要从题库中抽取m 道题组成试卷。并要求试卷包含指定类型的试题。试设计一个满足要求的组卷算法。 编程任务: 对于给定的组卷要求,计算满...

POJ 2135 Farm Tour (网络流,最小费用最大流)

POJ 2135 Farm Tour (网络流,最小费用最大流) Description When FJ's friends visit him on the farm, he likes to show them around. His farm comprises N (1 <= N <= 1000) fields numbered 1..N...

POJ 2516 Minimum Cost (网络流,最小费用流)

POJ 2516 Minimum Cost (网络流,最小费用流) Description Dearboy, a goods victualer, now comes to a big problem, and he needs your help. In his sale area there are N shopkeepers (marked from...

【codevs1034】家园——网络流

由数据范围看是可以用网络流的。。。 其实还是接近于很裸的网络流,不过是变成了动态建边,图会很大,不过题目数据范围小啊。。。 枚举时间,自己想一个上界,cyc大佬说是100,那就100吧,到达上界前找到就输出当前时间并退出,超出上界就输出0。 cyc大佬反复强调tot=1而不是2!!! 然后就跑啊跑,记得加当前弧优化! #include<cstdio&...