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

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;
}