iCMS

洛谷P2763题解

iCMS http://www.hlike.cn 2019-08-07 10:48 出处:网络 编辑:@iCMS
吐槽一下:蜜汁UKE是什么玩意?! 题目分析: 观察题面,对于给定的组卷要求,计算满足要求的组卷方案,可以发现这是一道明显的有条件的二分图匹配问题,于是考虑建模。

吐槽一下:蜜汁UKE是什么玩意?!

题目分析:

观察题面,对于给定的组卷要求,计算满足要求的组卷方案,可以发现这是一道明显的有条件二分图匹配问题,于是考虑建模。

建一个超级源点,一个超级汇点;源点与试题相连,汇点与类型相连。

重点是类型的题数的建模。可以从感性来理解一下,其实这有一点限流的意思,每个类型只要求有这么多的题量,不能超出,于是考虑在类型与汇点相连的时候将容量设为类型的题数,在算最大流的时候将题量限制住,就能满足题面的要求了。(希望大家能明白我的意思 (QwQ) )

最后的图即为:超级源点与试题相连,容量为1;类型与对应的试题相连,容量为1;类型与超级汇点相连,容量为类型的题数。具体来说,超级源点 (S) 为节点 (1),试题为节点 (2—n+1),类型为节点 (n+2—n+k+1) 超级汇点 (T) 为节点 (n+k+2) 。

建模完成之后,考虑记录方案。

因为 (Dinic) 算法是通过 (Xor;1) 来完成正向边与反向边的转变的,故正向边的 (e[i].to) 为路径终点,反向边的 (e[i;Xor;1].to) 为路径起点, 所以可以通过枚举每一条边来找到相应的节点。

又因为反向边的 (e[i;Xor;1].v) 的初始化为0,当 (e[i;Xor;1].vneq0) 时,即代表这条边是最大流跑过的边,也相当于这条边被匹配了。

最后排除掉超级源点与超级汇点的情况。

如果 (Dinic) 跑一遍下来,ans(即最大流)依然为0,则本数据没有答案(即输出"No Solution!")。

code(带详细注释):

#include<bits/stdc++.h>

#define Maxn 4010

#define Maxm 10010

#define int long long

using namespace std;

int k,n;

inline void read(int &x)

{

int f=1;x=0;char s=getchar();

while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}

while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}

x*=f;

}

int S,T;

int ans=0,dep[Maxn];

struct edge

{

int to,next,v;

}e[Maxm<<1];//一定注意要开两倍空间(正反两条边)

int head[Maxn],ei=1;//一定注意这里的ei为奇数

void add(int x,int y,int v)

{

ei++;

e[ei].to=y;

e[ei].v=v;

e[ei].next=head[x];

head[x]=ei;

}

int bfs()

{

queue<int>qu;

memset(dep,sizeof(dep));

dep[S]=1;

qu.push(S);

while(!qu.empty())

{

int fr=qu.front();

qu.pop();

for(int i=head[fr];i;i=e[i].next)

{

int to=e[i].to;

if(dep[to]!=0||e[i].v==0) continue;

qu.push(to);

dep[to]=dep[fr]+1;

}

}

return dep[T]!=0;

}

int dfs(int from,int maxflow)

{

if(from==T) return maxflow;

int flow=0;

for(int i=head[from];i;i=e[i].next)

{

int to=e[i].to;

if(dep[to]!=dep[from]+1||e[i].v==0) continue;

int rst=dfs(to,min(maxflow-flow,e[i].v));

if(rst==0) dep[to]=0;

e[i].v-=rst;

e[i^1].v+=rst;

flow+=rst;

if(flow==maxflow) break;

}

return flow;

}

void dinic()

{

while(bfs())

{

ans+=dfs(S,LLONG_MAX);

}

}

signed main()

{

read(k),read(n);

S=1,T=k+n+2;//超级源点与超级汇点

for(int i=1;i<=n;i++)

{

add(S,i+1,1);

add(i+1,S,0);

//超级源点与试题相连,容量为1

}

for(int i=1,x;i<=k;i++)

{

read(x);

add(i+n+1,T,x);

add(T,i+n+1,0);

//类型与超级汇点相连,容量为类型的题数

}

for(int i=1,p;i<=n;i++)

{

read(p);

for(int j=1,x;j<=p;j++)

{

read(x);

add(i+1,x+n+1,1);

add(x+n+1,0);

//类型与对应的试题相连,容量为1

}

}

dinic();//跑dinic

if(ans==0)//没有答案

{

puts("No Solution!");

return 0;

}

for(int num=1;num<=k;num++)//枚举所有类型

{

printf("%lld:",num);

for(int i=2;i<=ei;i+=2)//枚举每一条边来找到相应的节点

{

if(e[i].to!=S&&e[i].to!=T&&e[i^1].to!=S&&e[i^1].to!=T)//排除掉超级源点与超级汇点的情况

{

if(e[i^1].v!=0)//这条边已经被匹配了

{

if(e[i].to-n-1==num)//判断是否为当前类型

{

printf("%lld ",e[i^1].to-1);

}

}

}

}

printf("n");

}

return 0;

}

网络流注意事项:

网络流关键在于建模,精髓也在建模。像本题一样的二分图匹配问题可采取我使用的建模方式:最大匹配=最大流

前向星的计数器初始化时,一定要为奇数。因为第n条边为正向边,第n+1条边为反向边,要实现e[i]为正向边,e[i^1]为反向边,就要保证正向边的i为奇数,即计数器要初始化为奇数。

前向星边数一定要开两倍空间,因为正向边一条,反向边一条。

0

精彩评论

暂无评论...
验证码 换一张
取 消