洛谷P1231-教辅的组成(网络流+拆点)

题目链接:洛谷P1231-教辅的组成

题意:

n1本教材,n2本练习册,n3本答案,然后给定一些关系,问最多能组成多少组教材(教辅=教材+练习册+答案)

题解:

网络流裸题,但是要注意一本教材只能用一次,所以需要把每本教材拆成两个点,用流量为1的边相连即可。

具体连边方法:源点向练习册连边,练习册向教材连边,教材向拆分后的新教材连边,拆分后的新教材向答案连边,答案向汇点连边,以上边的流量全部为1,然后dinic即可。

参考代码:

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5;
const int MAXM = 1e6;
const int inf = 0x3f3f3f3f;
int n1, n2, n3, m1, m2, st, ed;
//源点 0;汇点 n1*2+n2+n3+1;
//书 n2+1 - n2+n1*2;
//练习册 1 - n2;
//答案 n1*2+n2+1 - n1*2+n2+n3;
struct EDGE
{
    int v, w, nxt;
} edge[MAXM * 2];
int cnt = 0, fir[MAXN];
void addedge(int u, int v, int w)
{
    edge[cnt].v = v;
    edge[cnt].w = w;
    edge[cnt].nxt = fir[u];
    fir[u] = cnt++;
}
int depth[MAXN],cur[MAXN];
int dfs(int u,int flow)
{
    if(u==ed)
        return flow;
    for(int& i=cur[u]; i!=-1; i=edge[i].nxt)
    {
        int v=edge[i].v;
        int w=edge[i].w;
        if(depth[v]==depth[u]+1&&w!=0)
        {
            int di=dfs(v,min(flow,w));
            if(di>0)
            {
                edge[i].w-=di;
                edge[i^1].w+=di;
                return di;
            }
        }
    }
    return 0;
}
bool bfs()
{
    queue<int> q;
    while(!q.empty())
        q.pop();
    memset(depth,0,sizeof(depth));
    depth[st]=1;
    q.push(st);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=fir[u]; i!=-1; i=edge[i].nxt)
        {
            int v=edge[i].v;
            int w=edge[i].w;
            if(depth[v]==0&&w>0)
            {
                depth[v]=depth[u]+1;
                q.push(v);
            }
        }
    }
    if(depth[ed]>0)
        return 1;
    else
        return 0;
}
int dinic()
{
    int tot=0;
    while(bfs())
    {
        for(int i=0; i<=n1*2+n2+n3+1; i++)
            cur[i]=fir[i];
        while(int temp=dfs(st,inf))
            tot+=temp;
    }
    return tot;
}
int main()
{
    scanf("%d%d%d", &n1, &n2, &n3);
    memset(fir, -1, sizeof(fir));
    cnt = 0;
    st = 0;
    ed = n1 * 2 + n2 + n3 + 1;
    for (int i = 1; i <= n2; i++)
        addedge(st, i, 1), addedge(i, st, 0);
    for (int i = 1; i <= n1; i++)
        addedge(i + n2, i + n2 + n1, 1), addedge(i + n2 + n1, i + n2, 0);
    for (int i = 1; i <= n3; i++)
        addedge(n1 * 2 + n2 + i, ed, 1), addedge(ed, n1 * 2 + n2 + i, 0);
    scanf("%d", &m1);
    for (int i = 1; i <= m1; i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        u += n2;
        addedge(v, u, 1);
        addedge(u, v, 0);
    }
    scanf("%d", &m2);
    for (int i = 1; i <= m2; i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        u += (n1 + n2);
        v += (n1 * 2 + n2);
        addedge(u, v, 1);
        addedge(v, u, 0);
    }
    int flow=dinic();
    printf("%d\n",flow);
    return 0;
}

发表留言

人生在世,错别字在所难免,无需纠正。