题目链接

题意:

给定n个英雄,m个怪兽,k个药水。

每个英雄只能杀死给定集合中的一个怪兽,使用药水后可以多杀一个,每个英雄最多使用一个药水。

题解:

1 - n表示英雄,n+1 - m+n 表示怪兽, 0表示起点(简称s点), n+m+1表示终点(t点),n+m+2表示K瓶药水所代表的点(kk点)。

起点 -> kk点的边,流量为k,其他边流量为1:象征最多使用k瓶药水。

kk点 -> 英雄点,流量为1:每个英雄最多使用一瓶药水。

怪兽点 -> t点,流量为1:每个怪兽最多只能被杀一次。

 图片来源

代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
const int maxm=1e6+5;
const int maxn=2005;
int n,m,k;
struct node{
    ll t,cap,flow,next;    //cap容量,flow流量
}e[maxm];
int head[maxn],cur[maxn],cnt; //cur优化dfs中的head
void add(int u,int v,int cap)   //u->v容量为cap
{

    e[cnt]=node{v,cap,0,head[u]};
    head[u]=cnt++;
    e[cnt]=node{u,0,0,head[v]};//容量为0的反向边
    head[v]=cnt++;
}
int dep[maxn];    //bfs深度
bool bfs(int s,int t)   //O(n+m)
{
    memset(dep,0,sizeof(dep));
    queue<int>q;
    q.push(s);
    dep[s]=1;
    while(!q.empty())
    {
        int u=q.front();q.pop();
        for(int i=head[u];~i;i=e[i].next)
        {
            int v=e[i].t;
            if(dep[v]==0&&e[i].cap-e[i].flow>0)
            {
                dep[v]=dep[u]+1;
                q.push(v);
            }
        }
    }
    return dep[t]>0;     //存在增广路
}
ll dfs(int s,int t,ll minedge)
{
    if(s==t)return minedge;
    ll flow=0;    //从当前s点流出的流量
    for(int &i=cur[s];~i;i=e[i].next)
    {
        int v=e[i].t;
        if(dep[v]==dep[s]+1&&e[i].cap-e[i].flow>0)   //层次关系&&有剩余流量
        {
            ll temp=dfs(v,t,min(minedge-flow,e[i].cap-e[i].flow));
            e[i].flow+=temp;    //流量增加
            e[i^1].flow-=temp;    //反向边流量减少
            flow+=temp;    //flow已分配的流量
            if(flow==minedge)return flow;  //已达到祖先的最大流,无法再大,剪枝
        }
    }
    if(flow==0)dep[s]=0;   //此点已无流,标记掉
    return flow;
}
ll dinic(int s,int t)   //一定要建立反向边cap=0
{
    ll maxflow=0;
    while(bfs(s,t))   //有增广路
    {
        memcpy(cur,head,sizeof(head));   //重要的优化
        maxflow+=dfs(s,t,inf);
    }
    return maxflow;
}
void init()
{
    memset(head,-1,sizeof head);
    cnt=0;
}
int main()
{
    int m, n, k;
    int x, y;
    init();
    scanf("%d %d %d", &n, &m, &k);
    int s = 0, t = n+m+1, kk = n+m+2;
    add(s, kk, k);
    for(int i = 1; i <= n; i++)
    {
        add(s, i, 1);
        add(kk, i, 1);
        scanf("%d", &x);
        for(int j = 0; j < x; j++)
        {
            scanf("%d", &y);
            add(i, y + n, 1);
        }
    }
    for(int i=1;i<=m;i++)add(i+n,t,1);
    int ans = dinic(s, t);
    printf("%d\n", ans);
    return 0;
}
邻接表
#include<bits/stdc++.h>//最大流
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int maxn=1055;
using namespace std;

int n, m, k;
int mmp[maxn][maxn];
int dep[maxn];
void add (int u, int v, int w)
{
    mmp[u][v] = w;
}
bool bfs (int s, int t)
{
    memset(dep, -1, sizeof(dep));
    queue<int> que;
    dep[s] = 0;
    que.push(s);
    while (!que.empty())
    {
        int u = que.front();
        que.pop();
        for (int i = 0; i < maxn; ++i)
        {
            int v = i;
            int flow = mmp[u][i];
            if (v != u && dep[v] == -1 && flow > 0)
            {
                dep[v] = dep[u] + 1;
                que.push(v);
            }

        }
    }
    return dep[t] != -1;
}

int dfs (int u, int t,int flow)
{
    if (u == t || flow == 0)
    {
        return flow;
    }
    int max_flow = 0, find_flow;
    for (int i = 0; i < maxn; ++i)
    {
        int v = i;
        int f = mmp[u][i];
        if (v != u && f > 0 && dep[v] == dep[u] + 1)
        {
            find_flow = dfs(v, t,min(flow - max_flow, f));
            if (find_flow > 0)
            {
                mmp[u][v] -= find_flow;
                mmp[v][u] += find_flow;
                max_flow += find_flow;
                if (max_flow == flow)
                    return flow;
            }
        }
    }
    if (max_flow == 0)
        dep[u] = -1;
    return max_flow;
}

int dinic (int s,int t)
{
    int max_flow = 0;
    while (bfs(s, t))
    {
        max_flow += dfs(s,t,inf);
    }
    return max_flow;
}

int main ()
{

    scanf("%d%d%d",&n,&m,&k);
    int s = 0, t = n + m + 1, kk = n + m + 2;
    memset(mmp, 0, sizeof(mmp));
    add(s, kk, k);
    for (int i = 1; i <= n; ++i)
    {
        add(s, i, 1);
        add(kk, i, 1);
        int x;
        scanf("%d",&x);
        for (int j = 0; j < x; ++j)
        {
            int v;
            scanf("%d",&v);
            add(i, n + v, 1);
        }
    }
    for (int i = 1; i <= m; ++i)
    {
        add(i + n, t, 1);
    }
    int ans = dinic(s,t);

    printf("%d\n",ans);
    return 0;
}
邻接矩阵
01-16 09:56