首页 > 代码库 > hihoCoder 1393 网络流三·二分图多重匹配 (网络流学习#3 记录)

hihoCoder 1393 网络流三·二分图多重匹配 (网络流学习#3 记录)

题目链接:http://hihocoder.com/problemset/problem/1393

 

话说我之前一直不知道二分匹配可以用网络流做。。。

技术分享
#include<cstdio>#include<cstring>#include<queue>using namespace std;const int N=205;struct ss{int v,c,nxt;} e[N*20];int head[N],tot,vis[N],n,m,a[N],b[N],sum,INF=0x3f3f3f3f,t;queue<int>q;void add(int u,int v,int c){    e[tot].c=c;    e[tot].v=v;    e[tot].nxt=head[u];    head[u]=tot++;    e[tot].c=0;    e[tot].v=u;    e[tot].nxt=head[v];    head[v]=tot++;}bool bfs(){    memset(vis,0,sizeof(vis));    vis[0]=1;    q.push(0);    int tmp,id;    while(!q.empty())    {        tmp=q.front();        q.pop();        for(int i=head[tmp]; i!=-1; i=e[i].nxt)        {            id=e[i].v;            if(vis[id]==0&&e[i].c)                vis[id]=vis[tmp]+1,q.push(id);        }    }    return vis[n+m+1];}int dfs(int node,int c){    if(node==t||c==0)        return c;    int ans=0;    for(int i=head[node]; i!=-1; i=e[i].nxt)    {        int id=e[i].v,kk;        if(vis[id]==vis[node]+1)        {            kk=dfs(id,min(c,e[i].c));            if(kk>0)            {                e[i].c-=kk;                e[i^1].c+=kk;                ans+=kk;                c-=kk;                if(c==0)                    return ans;            }        }    }    return ans;}int mf(){    int ans=0;    while(bfs())    {        ans+=dfs(0,INF);    }    if(ans!=sum)        return 0;    return 1;}int main(){    int T;    scanf("%d",&T);    while(T--)    {        int x=0;        memset(head,-1,sizeof(head));        tot=0;        sum=0;        scanf("%d%d",&n,&m);        t=n+m+1;        for(int i=1; i<=m; i++)        {            scanf("%d",&x);            add(n+i,t,x);            sum+=x;        }        for(int i=1; i<=n; i++)        {            scanf("%d%d",&a[i],&b[i]);            add(0,i,a[i]);            for(int j=0; j<b[i]; j++)            {                scanf("%d",&x);                add(i,x+n,1);            }        }        if(mf())            puts("Yes");        else            puts("No");    }}
View Code

(邻接表)
昨天邻接表打了一发,然后今天邻接矩阵就卡了,wa了半天,然后发现我初始化有问题,。,。郁闷。

技术分享
#include<bits/stdc++.h>using namespace std;const int maxn=205,INF=0x3f3f3f3f;int n,m,a[maxn],b[maxn],mm[maxn],s=0,t,c[maxn][maxn],pre[maxn],flow[maxn];int bfs(){    int tmp;    memset(pre,-1,sizeof(pre));    memset(flow,0,sizeof(flow));    queue<int>q;    q.push(s);    flow[s]=INF;    while(!q.empty())    {        tmp=q.front();        q.pop();        if(tmp==t)            return flow[t];        for(int i=1;i<=t;i++)        {            if(pre[i]==-1&&c[tmp][i]>0)            {                pre[i]=tmp;                flow[i]=min(flow[tmp],c[tmp][i]);                if(flow[i]!=0)                    q.push(i);            }        }    }    return 0;}void work(){    int ans=0;    int tmp;    while(bfs())    {        tmp=t;        while(tmp!=s)        {            c[pre[tmp]][tmp]-=flow[t];            c[tmp][pre[tmp]]+=flow[t];            tmp=pre[tmp];        }        ans+=flow[t];    }    if(ans!=mm[0])        puts("No");    else        puts("Yes");}int main(){    int T,tmp;    scanf("%d",&T);    while(T--)    {        scanf("%d%d",&n,&m);        t=n+m+1;        mm[0]=0;        memset(c,0,sizeof(c));        for(int i=1;i<=m;i++)        {            scanf("%d",&mm[i]);            c[n+i][t]+=mm[i];            mm[0]+=mm[i];        }        for(int i=1;i<=n;i++)        {            scanf("%d%d",&a[i],&b[i]);            c[s][i]+=a[i];            for(int j=1;j<=b[i];j++)            {                scanf("%d",&tmp);                c[i][n+tmp]+=1;            }        }        work();    }}
View Code

(邻接矩阵)
我感觉我现在网络流已经入门了。。。然而还是不知道 什么时候该用哪个,,比如我做下一题的时候就直接用了ek那个我就超时了。。。然后改成分层的。。

hihoCoder 1393 网络流三·二分图多重匹配 (网络流学习#3 记录)