( 一 ) 如果x部节点只对应一个y部节点,而y部节点可以对应多个x部节点,那么这种匹配可以用匈牙利算法来解决。
如何解决?
方法一:
我们知道,传统的二分匹配是一对一匹配的,那么我们把y节点拆点,然后再按照正常的二分匹配就可以了。
这样做的问题是:当y节点很大时,那么拆点耗费的时间会很多!
方法二:
把y部节点的match数组改为二维的,第一维度表示第i个y节点,第二个维度表示这个y节点剩余的容量
G - Escape
题意:
有N(N<100,000)个人要去M(M<10)个星球，每个人只可以去一个星球，一个星球最多容纳Ki个人。请问是否所有人都可以选择自己的星球
题解:
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int MAXN=100010;
int cnt[15],cap[15];//cap为y节点的容量,cnt为当前y节点使用的容量
int graph[MAXN][15];
int n,m,used[15];
int match[15][MAXN];
//match[i][j]=k 第i个星球上住的第j个人是k
bool DFS(int x)
{
for(int i=1;i<=m;i++)
{
if(graph[x][i]&&used[i]==0)
{
used[i]=1;
if(cnt[i]<cap[i])//如果当前y节点还有容量可以匹配
{
cnt[i]++;
match[i][cnt[i]]=x;
return true;
}
for(int j=1;j<=cnt[i];j++)//如果y节点的容量已经满了,尝试为y节点的某个对象换对象
{
if(DFS(match[i][j]))
{
match[i][j]=x;//y节点第j个位置让给x
return true;
}
}
}
}
return false;
}
bool judge()
{
memset(cnt,0,sizeof(cnt));
for(int i=1;i<=n;i++)//为所有x节点匹配对象
{
memset(used,0,sizeof(used));
if(!DFS(i)) return false;
}
return true;
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
scanf("%d",&graph[i][j]);
}
}
for(int i=1;i<=m;i++)
{
scanf("%d",&cap[i]);
}
if(judge()) printf("YES\n");
else printf("NO\n");
}
return 0;
}
( 二 )如果x部节点可以匹配多个y部节点,y部节点可以同时匹配多个x部节点,那么应该用网络流来解决。(因为匈牙利算法无法应对两边都可以选多个这种情况)
怎么建图?
很简单,假设x部节点的容量为capx[ i ],y部节点的容量为capy[ i ],同时给出x部节点可以与y部节点相连的的边,那么对于每个x部节点,超级源点都与x部节点连边,边权为capx[i];对于每个y部节点,都与超级汇点连接边,边权为capy[i]。然后连接每个x与y直接相连的边,边权为1。
From hihocoder
这样一来,求出最大流就是最大匹配方案了:流量通道上的边的剩余流量代表匹配结果
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<queue>
using namespace std;
const int MAXN=250;
const int MAXE=20010;
const int INF=0x3f3f3f3f;
struct Node
{
int to,next,val;
Node(int to,int next,int val):to(to),next(next),val(val){};
Node(){}
};
Node edge[MAXE];
int head[MAXN],cnt;
void addEdge(int u,int v,int val)
{
edge[cnt]=Node(v,head[u],val);head[u]=cnt++;
edge[cnt]=Node(u,head[v],0);head[v]=cnt++;
}
int step[MAXN];
bool BFS(int st,int ed)
{
memset(step,-1,sizeof(step));
step[st]=0;
queue<int> que;
que.push(st);
while(!que.empty())
{
int u=que.front();que.pop();
for(int i=head[u];i!=-1;i=edge[i].next)
{
int v=edge[i].to;
if(edge[i].val>0&&step[v]==-1)
{
step[v]=step[u]+1;
que.push(v);
if(v==ed) return true;
}
}
}
return false;
}
int DFS(int st,int ed,int flow)
{
if(st==ed||flow==0) return flow;
int curr=0;
for(int i=head[st];i!=-1;i=edge[i].next)
{
int v=edge[i].to;
if(step[v]==step[st]+1&&edge[i].val>0)
{
int d=DFS(v,ed,min(flow,edge[i].val));
if(d>0)
{
edge[i].val-=d;
edge[i^1].val+=d;
flow-=d;
curr+=d;
if(flow==0) break;
}
}
}
if(curr==0) step[st]=INF;
return curr;
}
int Dinic(int st,int ed)
{
int flow=0;
while(BFS(st,ed))
{
flow+=DFS(st,ed,INF);
}
return flow;
}
int main()
{
int t,n,m,st,ed,need,num,good,item,sum;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
sum=cnt=0;st=n+m+1;ed=st+1;
memset(head,-1,sizeof(head));
for(int i=1;i<=m;i++)
{
scanf("%d",&need);
sum+=need;
addEdge(n+i,ed,need);
}
for(int i=1;i<=n;i++)
{
scanf("%d%d",&num,&good);
addEdge(st,i,num);
for(int j=1;j<=good;j++)
{
scanf("%d",&item);
addEdge(i,n+item,1);
}
}
int res=Dinic(st,ed);
if(res!=sum) printf("No\n");
else printf("Yes\n");
}
}
