「网络流24题」试题库问题

发表于 | 分类于 | | 浏览量： 次

又是一道经典题。

传送门

洛谷P2763

LOJ6006

题解

考虑如何建模。

很显然这是一个二分图。

对于题库中的每一道题，像试卷中的所有可行的空位连边。

比如题库中一道题可以属于$1$类或者$2类$，那么就往试卷中所有$1类$和$2$类的位置连边。

由于一道题只能用在试卷上的一个位置，且试卷上的一个位置也只能放一道题。

所以直接上匈牙利算法求解该二分图的最大匹配即可。

当最大匹配数小于$m$时即为无解。（洛谷上的数据真水，一开始我没考虑无解的情况竟然AC了）

也可以转化成最大流问题，然后用EK、Dinic等求解。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=1005;
int k,st[maxn],grp[maxn],n,m,tot,lnk[maxn],son[maxn*maxn],nxt[maxn*maxn],cp[maxn],len[maxn],A[25][maxn],sum;bool vis[maxn];
inline int read()
{
	int ret=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
	while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=getchar();}
	return ret*f;
}
inline void add_e(int x,int y){tot++;son[tot]=y;nxt[tot]=lnk[x];lnk[x]=tot;}
bool Hungary(int now)
{
	for(int i=lnk[now];i;i=nxt[i])
	{
		if(!vis[son[i]])
		{
			vis[son[i]]=true;
			if(!cp[son[i]]||Hungary(cp[son[i]]))
			{
				cp[son[i]]=now;
				return true;
			}
		}
	}
	return false;
}
int main()
{
	k=read();n=read();
	for(int i=1;i<=k;i++)
	{
		int cnt=read();st[i]=m+1;
		for(int j=1;j<=cnt;j++) grp[++m]=i;
	}
	for(int i=1;i<=n;i++)
	{
		int cnt=read();
		for(int j=1;j<=cnt;j++)
		{
			int to=read();
			for(int k=st[to];grp[k]==to;k++) add_e(i,k);
		}
	}
	for(int i=1;i<=n;i++){memset(vis,false,n+3);Hungary(i);}
	for(int i=1;i<=m;i++)
		if(cp[i])
			{len[grp[i]]++;A[grp[i]][len[grp[i]]]=cp[i];}
	for(int i=1;i<=k;i++) sum+=len[i];
	if(sum<m){printf("No Solution!");return 0;}
	for(int i=1;i<=k;i++)
	{
		printf("%d:",i);
		for(int j=1;j<=len[i];j++)
			printf(" %d",A[i][j]);
		printf("\n");
	}
	return 0;
}